学習する天然ニューラルネット

主に機械学習に関する覚書や情報の整理。競プロ水色→Kaggle Master→?

競技プログラミング

AtCoderでCythonの力を開放する魔術詠唱

概要 以下のformatをPythonで提出すればいい mycode = r''' # distutils: language=c++ # cython: language_level=3, boundscheck=False, wraparound=False, cdivision=True {ここにcythonのコードを書く} ''' import sys import os if sys.argv[-1] == 'ONL…

AtCoderでPythonが再帰に弱い問題をどうにかしたい

概要 目次 概要 背景 解決法 速度比較 PythonとPypyの回答 Cythonの回答 Cythonを使いやすく 今回のオチ まとめ 本記事の貢献 Python, Pypy, Cythonにおける再帰関数の速度比較 cythonをscript感覚で動かすコマンドの作成 (stackで書き換えるのが一番早かっ…

Mo's algorithm のPython実装 (コピペ用)

この記事はなに? Mo's algorithmについてPythonでの実装が検索に引っかからなかったので、(自分のメモも含めて)ここに実装をおいておく。 コンテストに向けてコピペで済むように心がけた。 Mo's algorithmとは? このブログにたどり着いてる時点で多くを語る…

蟻本Python回答集 中級前編 (P127~P187)

はじめに AtCoder青を目指しつつデータ構造など勉強するため、プログラミングコンテストチャレンジブック [第2版] ■ (通称、蟻本)を解くことした。 せっかくなのでPythonでの解答をここに記録する。 Pythonで解答してる人のブログを漁っても初級編の途中(DP…

蟻本Python回答集 初級編 (~P126)

はじめに とうとうAtCoder水色になれた(過去問精進と夜活コンテストのおかげ)。さらなる高みを目指すべく、プログラミングコンテストチャレンジブック [第2版] (通称、蟻本)を解くことした。 せっかくなのでPythonでの解答をここに記録する。 Pythonで解答し…

らくらくp進全探索 コピペで使えるPython実装

何をしたか? 連続するp進数を次々返してくれるiteratorを実装しました(といっても標準ライブラリにラップしただけ)。 例えば、3桁の3進数だったら000, 001, 002, 010, 012 ..., 222 というものを次々に返してくれます。 実際には桁ごとにリストの1要素を構…

降順リストに対するbisectの実装 list.sort(reverse=True)に対する配列二分法

はじめに Pythonにおいて、降順リスト向けの配列二分法アルゴリズムを実装しました。 使用するメリット コピペで標準ライブラリに準拠した動作をします。 標準ライブラリと異なり、降順リストを扱います。 昇順リストに変換し直す計算量と、昇順のidxを降順…

めぐる式二分探索 コピペで使えるPython実装

はじめに めぐる式二分探索のメリットと参考文献 コピペ用 例題 はじめに AtCoderで二分探索を実装するときバグらせないように考えると結構時間かかりませんか?自分はかかります。 競技プログラミング界隈ではめぐる式二分探索という二分探索の書き方(流派…

螺旋本をPythonで解く Part4

はじめに 17章 動的計画法 P412 DPL_1_A: Coin Changing Problem P416 DPL_1_B: 0-1 Knapsack Problem P421 DPL_1_D: Longest Increasing Subsequence P425 DPL_3_A: Largest Square P428 DPL_3_B: Largest Rectangle 18章 整数論 P436 ALDS_1_C: Prime Numb…

螺旋本をPythonで解く Part3

はじめに 14章 高度なデータ構造 P318 DSL_1_A: Disjoint Set: Union Find Tree P324 DSL_2_C: Range Search (kD Tree) 15章 高度なグラフアルゴリズム P336 GRL_1_C: All Pairs Shortest Path P342 GRL_4_B: Topological Sort P348 GRL_3_A: Articulation P…

螺旋本をPythonで解く Part2

はじめに 8章 木 P188 ALDS1_7_A: Rooted Trees P193 ALDS1_7_B: Binary Tree P198 ALDS1_7_C: Tree Walk P203 ALDS1_7_D: Reconstruction of the Tree 9章 二分探索木 P209 ALDS1_8_A: Binary Search Tree 1 P214 ALDS1_8_B: Binary Search Tree 2 P217 ALD…

螺旋本をPythonで解く Part1

はじめに 2章 アルゴリズムと計算量 P46 ALDS1_1_D: Maximum Profit 3章 初等的整列 4章 データ構造 P82 ALDS1_3_A: Stack P87 ALDS1_3_B: Queue P95 ALDS1_3_C: Doubly Linked List P114 ALDS1_3_D: Areas on the Cross-Section Diagram 5章 探索 P119 ALDS…