競技プログラミング

限られた時間の中で問題を解くために必要となる、競技プログラミングにおける基本的な処理のチートシートです。競プロにおけるメジャー言語 C++ を利用します。その際 C++11 の機能は利用せず C++03 の機能の範囲内で記述します。 頻度高く定期的に開催されるコンテスト AtCoder Codeforces main.cpp #include <iostream>

最大公約数 (greatest common divisor; gcd) 自然数 a と b が a >= b ならば a = p*b + q (b > q) となる整数 p と q が存在します。b を割り切る整数 (b の約数) のうち q を割り切る整数 (b と q の公約数) ならば a も割り切ります。また a と b の最大公約数が b を越えることはありません。そのため...

用語 共通の用語 vertex, node 頂点 edge 辺 頂点の次数 頂点につながっている辺の数 パス 隣接している頂点を結んでいった経路 閉路 始点と終点が同じパス 特殊なグラフの用語 二部グラフ 隣接する頂点を異なる色で彩色するとき、必要な最小の色数が 2 であるグラフ 連結グラフ 任意の頂点間にパスが存在するグラフ 重み付きグラフ 辺に cost 重みがある

『プログラミングコンテストでのデータ構造』で紹介されている Union-Find 木で集合を表現すると、以下のクエリを高速に実行できます。集合一つが一つの木となるため、複数の集合がある場合は全体として森になります。 ある要素 a_i と a_j が同じ集合に属しているかどうかの判定 二つの集合を一つの集合にまとめる サンプル [POJ 1182](https://translat

サンプルコード ソートされた長さ N の配列 a_i は有界な順序集合です。有界な順序集合には上界 upper_bound と下界 lower_bound があります。a_i は upper_bound によって上から押さえつけられています。lower_bound によって下から押さえつけられています。 #include <iostream> #include <algorith...

部分問題を解きまくって、問題を解く手法です。DFS 全探索とは発想が異なり、例えば i が大きい後ろからある種の全探索します。部分問題の結果をメモリに格納 (メモ化) しておき、より大きな部分問題を解くときに利用します。 問題文を図にしてみる i の大きい後ろに限定した部分問題を見つける i 番目を「とれる (とる, とらない), とれない」で場合分けして漸化式を得る 端が定数 (0 など) にな...

サンプルコード #include <iostream> #include <algorithm> // next_permutation のため。 using namespace std; const int MAXN = 1024; bool used[MAXN]; int perm[MAXN]; int perm2[MAXN]; // 表示用関数 void displa...

頂点数nが小さい場合に限れば、巡回セールスマン問題はビットDPの手法でうまく解くことができます。 サンプルインプット 頂点数n (<=15)、辺の数mの重みつき有向グラフがあり、最初頂点0にいるとします。すべての頂点を訪れて頂点0に戻ってきたときの重みの総和の最小値を求めましょう。 n(頂点数) m(辺の数) Vi1 Vj1 cost1 Vi2 Vj2 cost2 ... Vim Vjm c...

頂点数nで、辺の数がmのグラフが与えられているとする。隣接する頂点同士が違う色になるように二色で塗り分けられるならばそのグラフを二部グラフという。 判定するグラフ n m V_i1 V_j1 V_i2 V_j2 ..... V_im V_jm 1行目は頂点数nと辺の数m、2行目からm+1行目まではそれぞれ頂点V_iと頂点V_jが辺で結ばれていることを示す。 判定プログラム例 二部グラフであれば"Y...