競技プログラミングにおける典型問題は、新たに学習したアルゴリズムを実装して試すとき、
あるいはライブラリを作成して試すときなどに利用すると最適です。
これまでに経験した範囲で、分野ごとに典型問題と思われるものを以下にまとめました。
AtCoder の緑～水ランク前後の人であれば利用する機会が多いのではないでしょうか。
サイト
- Courses | Aizu Online Judge
- AOJ のコースには典型問題が分野ごとに用意されています。
- 書籍 プログラミングコンテスト攻略のためのアルゴリズムとデータ構造 に詳しい解説があります。
- AtCoder Tags
- 分野から問題を探すにはこちらのサイトが便利です。
典型問題が多く出題されたコンテスト
- 競プロ典型 90 問
- アルゴリズム実技検定 (PAST)
- AtCoder Typical Contest 001
- AtCoder Typical Contest 002
- AtCoder Library Practice Contest
- Chokudai SpeedRun 001
- Chokudai SpeedRun 002
- Typical DP Contest (2013)
- Educational DP Contest (2019)
- ABC 153
アルゴリズム別
データ構造
最長増加部分列 (LIS)
動的計画法 (DP)
bit DP
木 (Tree)
Union-Find 木
優先度付きキュー (priority queue)
区間木 (セグメント木, segment tree)
最短経路問題
Dijkstra 法
巡回セールスマン問題
最大流問題
最大流・最小カット
- QUPC 2014 H - お風呂は気持ちいい
- 有向グラフ
- 一部の言語では入力データに空行 (?) が含まれており、RE (実行時エラー) になるため注意
- ABC 010 D - 浮気予防
- 無向グラフ
二部マッチング
グラフ (その他)
Euler Tour
