頻出アルゴリズムの練習について
競技プログラミングやプログラミングコンテスト等においては、やや複雑なアルゴリズムが頻出する一方、普段のプログラミング環境とは異なる条件や基準で実装が求められる。
- 実装に制限時間がある。そのためバグなしで正確に、高速に実装する必要がある。
- プログラムの実行回数、もしくは実行自体に制限がある。そのため、脳内で動作検証をする必要がある。
- エッジケースを洗い出し、必要十分なテストケースを考え、動作検証する必要がある。
- IDEやデバッカのサポートが使えない
このようなより人間の能力が試される環境である一方、やや複雑なアルゴリズムも含まれる。これも大会や環境によるが、例えば、 Union-find、Topological sorting、Quickselect などである。
こういった頻出でやや複雑なアルゴリズムについては、事前に何度か実装しておき、いざ必要になったときにすぐ正確に高速に実装できるようにする、実装練習が有効なのではと考え、それの練習環境を整備することにした。
注意
競技プログラミングで試される能力は、論理的思考力であったり、適切なアルゴリズムやデータ構造を選択し実装できること、計算量の算出や削減がメインだと思われる。上記の対策はあくまでも「比較的頻出な、やや複雑なアルゴリズムを高速に実装」できるようにするものであり、メインの能力のトレーニングは別途必要であり、かつそちらのほうが重要であるだろう。
提案する実装練習
- 練習対象とするアルゴリズムを選定する
- 毎日一つランダムにピックアップして実装練習する
- このときなるべく本番に近い環境で行う(プログラムを実行しない、IDEを使わない、等)
- 脳内で必要十分なテストケースを考え、動作検証する
- 最後に実際にプログラムを実行し、テストケースを走らせて、本当に正しく実装できたか最終確認とする
この最後の4に利用する目的のテストケースを、頻出と思われるアルゴリズムについて整備したので公開します。
アルゴリズムの関数の宣言だけ書いたmockも含めているので、コピーして簡単に実装練習できるようになっています。
avvmoto/Python-Popular-Algorithm-Testcases
$ ruby -e 'puts ["bellman_ford", "washall_floyd", "dikstra (array)","dikstra (priority queue)","quick sort", "quick select", merge sort", "union find","toporogical sort","binary_search"].sample'
bellman_ford
$ cp mock/bellman_ford.py .
# edit ./bellman_ford.py and implement Bellman–Ford algorithm
なお実装にあたっては1、2を参考にさせていただきました。ありがとうございます。
自分が練習対象に選んだアルゴリズムは以下の通りです。個人の主観で選んでいるので、追加PR等お待ちしております。
- Shortest Path
- Floyd–Warshall algorithm
- Bellman–Ford algorithm
- Dijkstra's algorithm
- Sort
- Quicksort
- Merge sort
- Quickselect
- Union-find
- Topological sorting
- Binary search
実装練習のバリエーション
Shortest path
重み付きグラフでの最短経路問題について、自分は3つ実装練習に入れている。実装練習にあたっては、計算量や、使い分けを振り返ってから行っている。
- Floyd–Warshall algorithm
- すべての2頂点間の最短路を求めるアルゴリズム
- 負の重みの辺があっても利用でき、負閉路の有無を判別できる
- 計算量は $O(|V|^3)$
- 実装が一番簡単なので、計算量が許すのであれば、単一始点最短経路問題を解くのにも利用したい2
- Bellman–Ford algorithm
- 単一始点最短経路を解くアルゴリズム
- 負の重みの辺があっても利用でき、負閉路の有無を判別できる
- 計算量は $O(|V||E|)$
- Dijkstra's algorithm
- 単一始点最短経路を解くアルゴリズム
- 辺の重みはすべて非負の場合に利用可能
- 計算量は $O(|E|log|V|)$ (Priority Queueを使う場合)、もしくは $O(|V|^2)$ (arrayを使う場合)
Topological sorting
- Topological sorting の解き方には、DFSやKahn's algorithmがある。計算量はどちらも同じなのでどちらで解いてもよいのだが、Kahn's algorithmのほうが自然に解けそうな問題も体験した。テストケースとしては両方同じなので、交互に実装してみても良い。
- 与えられた入力が不正で、循環がありTopological sortingが定義できないパターンもある。これの実装練習用のテストケースも書いてもいいかも(TODO)。
Union-find
- テストケースのリポジトリでのUnion-findの実装では、計算量を削減する工夫を入れている。ただし$N$が小さく、最悪実行時間の$O(N)$が許容できる場合、以下のようにより短くシンプルに実装することもできる。テストケースとしては同じになるので、たまにはこちらを実装してみるのも良い。
N = 10
parent = list(range(N))
def root(a: int) -> int:
if parent[a] != a:
parent[a] = root(parent[a])
return parent[a]
def unite(a: int, b: int) -> None:
a = root(a)
b = root(b)
parent[b] = a
return
Doubly linked list
- Doubly linked list 自体は標準ライブラリ collections.OrderedDict にあり、ユースケースが充分ならこちらも使えるようにしておきたい。
TODO
題材になっている課題を目撃したので、実装練習の対象に追加しようと思っているもの