競プロのアルゴリズムまとめ

素数系アルゴリズム:エラトステネスの篩

今回は、素数に関するアルゴリズムのうちの基礎中の基礎、エラトステネスの篩です。 唐突ですが、ある自然数 に対し、 が素数であるか否かの判定は で計算することができます。 以下証明です。 が素数でない場合、つまり が 以外の自然数 で割り切れる場合、…

グラフ探索アルゴリズム:深さ優先探索の帰りがけ deque 実装版

以前の記事で、deque を使った深さ優先探索と幅優先探索の python スクリプトや、再帰関数をつかった深さ優先探索の行きがけと帰りがけの python スクリプトをご紹介しました。 deque による深さ優先探索は、前回の記事では行きがけの実装のみの記載となって…

DP:フィボナッチ数、階乗、組み合わせ数

タイトルには DP と付けましたが、どちらかというと計算のメモ化の色が強いです。 今回は、あると便利なフィボナッチ数、階乗、組み合わせ数の計算スクリプトをご用意したので記事にいたします。 コンテストに参加していると、ふとした瞬間に「階乗を計算す…

グラフ系アルゴリズム:Union-Find 木

先日書いた記事の katoufujibanana.hatenadiary.jp にて、グラフ上のある2点が接続しているかどうかの判定アルゴリズムとして、Union-Find の名前を出しましたが、どのようなアルゴリズムだったかは触れなかったので今回は Union-Find を取り上げます。 ま…

グラフ+bitDP:巡回セールスマン問題

今回は巡回セールスマン問題(Traveling Salesman Problem: TSP)のコードを書きます。グラフ上のすべてのノードをめぐる最小距離を求める問題です。どちらかというとグラフの探索アルゴリズムというよりかは、DP 的側面の強いアルゴリズムという印象。 素朴…

グラフ探索アルゴリズム:深さ優先探索の行きがけと帰りがけ

グラフを探索するアルゴリズム、深さ優先探索。英語でいうと Depth-first Search (DFS)。深さ優先探索にはタイトルの通り、行きがけと帰りがけのバリエーションがあります。 前回の記事では Python の deque クラスを使用した、深さ優先探索と幅優先探索の実…

グラフ探索アルゴリズム:深さ優先探索と幅優先探索

グラフを探索するアルゴリズム、深さ優先探索と幅優先探索。 英語でいうと Depth-first Search (DFS)、Breadth-first Search (BFS)。 競技プログラミング頻出のアルゴリズム(基礎レベル?)ですが、知らないと自力でひらめくのは難しいはず。いわゆる”知識”…