競技プログラミングの典型テクニック

AtCoder「競プロ典型 90 問」精進で出会った、定石となるアルゴリズム・考察パターンの引き出し。最適解が定まる問題系(ヒューリスティックと対になる)。_moc-algorithm

グラフ

• 強連結成分分解 (SCC): ① 各頂点から DFS し帰りがけ順に番号付け ② 辺を逆にしたグラフを番号の大きい順に DFS。逆辺にすることでループ以外を遮断する。
• 木 DP / 全方位: 子孫の数を DFS で求め、各辺の貢献度を総和する(= 主客転倒、和の取り方を入れ替える発想)。
• 木の直径: 任意点から BFS → 最遠点から再度 BFS。最短路 ダイクストラも始点を両端に取って 2 回。
• 01-BFS: 辺重みが 0/1 のときデック BFS で最短路。

動的計画法 (DP)

• DP の高速化: 区間 max/min の遷移を セグメント木の RMQ クエリに帰着して $O(N)$ 改善。座標圧縮 + 遅延セグメント木の併用も典型。
• DP 復元: 遷移元を辿って解を構築。見る行のずれに注意。
• 桁/和 DP: 「和が $K$」を ${\sum }_i(i+\text{和が }K-i)$ のように分解。
• 半分全列挙 (meet in the middle): $O(2^N)\to O(N\cdot 2^{N/2})$。集合を半分に割って列挙・マージ。
• → knapsack-dp

配列・区間

• いもす法: 区間加算を差分で $O(1)$、最後に累積和。二次元版もある。
• 尺取り法: 単調性のある区間を両端ポインタで走査。
• LIS (最長増加部分列): 各点を山頂にした両側 LIS で $P_i+Q_i-1$ のような構成も。
• 座標圧縮: 値域が疎なとき添字を詰める前処理。

数学・その他

• マンハッタン距離の 45°回転: $(x+yi)(1+i)=(x-y)+(x+y)i$ でチェビシェフ距離に変換。
• 期待値の線形性: $E[X+Y]=E[X]+E[Y]$ で独立性不要に分解。
• 周期性: 状態が有限なら必ずループする。Floyd / 周期検出。
• 素因数を 1 つずつ足すような構成的列挙。

実装ノート

Python で TLE するとき、JIT の暖機オーバーヘッドで Julia も間に合わず C++ に落とす、という言語選択の現実もある。

関連

• atcoder / competitive-programming-heuristics
• segment-tree / strongly-connected-components / knapsack-dp