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

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

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

競技プログラミング

何をしたか？

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

1種類あたりp個の選択肢があり、n種に対して全探索したい場合、これをn桁のp進全探索と呼ぶことにします。 この全探索を生成するコードは以下です。

続きを読む

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

競技プログラミング

はじめに

Pythonにおいて、降順リスト向けの配列二分法アルゴリズムを実装しました。

使用するメリット

  • コピペで標準ライブラリに準拠した動作をします。
  • 標準ライブラリと異なり、降順リストを扱います。
  • 昇順リストに変換し直す計算量と、昇順のidxを降順のidxに変換する思考リソースを削減します
続きを読む

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

競技プログラミング
  • はじめに
  • めぐる式二分探索のメリットと参考文献
  • コピペ用
  • 例題

はじめに

AtCoderで二分探索を実装するときバグらせないように考えると結構時間かかりませんか？自分はかかります。

競技プログラミング界隈ではめぐる式二分探索という二分探索の書き方(流派？)があり、使いやすい、バグりにくくなど様々なメリットがあります。

Python実装を公開しているブログはパット見、見つからなかったのでおいておきます。使用例もおいておきます。

めぐる式二分探索のメリットと参考文献

めぐる式二分探索を使うメリットとして以下があげられます。

  • 配列化できない関数を探索可能 (bisectモジュールでは不可)
  • バグりにくい (終了状態がきちんとしている)
  • ライブラリとして扱うことが可能で実装が高速化される
  • 思考リソースの消耗を防げる (条件を満たすかそうでないかだけ考えれば良い)
続きを読む

螺旋本を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 Numbers
    • P441 ALDS1_1_B: Greatest Common Divisor
    • P445 NTL_1_B: Power
  • 19章 ヒューリスティック探索 (省略)
  • 終わりに
続きを読む

螺旋本を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 Point
    • P353 GRL_5_A: Diameter of a Tree
    • P358 GRL_2_A: Minimum Spanning Tree
  • 16章 計算幾何学
    • P384 CGL_1_C: Counter-Clockwise
    • P387 CGL_2_B: Intersection
    • P398 CGL_3_C: Polygon-Point Containment
    • P401 CGL_4_A: Convex Hull
    • P405 CGL_6_A: Segment Intersections: Manhattan Geometry
  • つづく
続きを読む

螺旋本を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 ALDS1_8_C: Binary Search Tree 3
  • 10章 ヒープ
    • P234 ALDS1_9_A: Complete Binary Tree
    • P236 ALDS1_9_B: Maximum Heap
    • P240 ALDS1_9_C: Priority Queue
  • 11章 動的計画法
  • 12章 グラフ
    • P269 ALDS1_11_A: Graph
    • P273 ALDS1_11_B: Depth First Search
    • P282 ALDS1_11_C: Breadth First Search
    • P287 ALDS1_11_D: Connected Components
  • 13章 重み付きグラフ
    • P296 ALDS1_12_A: Minimum Spanning Tree
    • P302 ALDS1_12_B: Single Source Shortest Path 1
    • P309 ALDS1_12_C: Single Source Shortest Path 2
  • つづく
続きを読む

螺旋本を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 ALDS1_4_A: Linear Search
    • P122 ALDS1_4_B: Binary Search
    • P127 ALDS1_4_C: Dictionary
    • P136 ALDs1_4_D: Allocation
  • 6章 再帰・分割統治法
    • P142 ALDS1_5_A: Exhaustive Search
    • P146 ALDS1_5_C: Koch Curve
  • 7章 高等的整列
    • P152 ALDS1_5_B: Merge Sort
    • P158 ALDS1_6_B: Partition
    • P163 ALDS1_6_C: Quick Sort
    • P168 ALDS1_6_A: Counting Sort
    • P175 ALDS1_5_D: The Number of Inversions
    • P179 ALDS1_6_D: Minimum Cost Sort
  • つづく
続きを読む