競技プログラミングで出てきそうな問題パターンの考察

• シミュレーション
• 言われたとおりにシミュレーションをする。
• 考え方を変えれば少し上手い方法があるかも。
• 全探索
• 深さ優先探索・幅優先探索、ビットフラグなど使いとりあえず全探索する。
• 陽に解を検索する
• 算数的・数学的にうまくできそうだけども、考え方を変えて解候補を探索する方法
• 全体の$K$個目を求めるときなどに使えるかも。
• $f(x)$が単調増加する場合に、$x$自体を二分探索し、$f(x)=A$になるものを見つけるなど
• 思いつかない事が多い（運営者は）
• 頭の体操問題
• 工夫をすれば簡単になる問題
• 全探索と思わせて
• いくつか変数を決めると他の変数も決まる問題。　x+y=10みたいな方程式を考えると良い
• 二分探索：単調増加な関数のある値になるような場所を求める。最小値最大化、平均値最小化などは二分探索＋貪欲法で解ける可能性が高い
• 三分探索：凸な関数の最小値を求める。
• 配列が与えられて、ある規則を満たすものがあれば消していく問題。
• 無限ループの中でreplaceやremoveをして、replaceができなくなったら抜ける。
• もしくはキューを使ってのプッシュダウンオートマトンを実装する。
• 配列が与えられて、順番に追加したり、最大のものを表示または削除するのを何度かする
• 優先度付きキュー(priority queue)
• 数え上げ問題
• 数学的なら、コンビネーション P,C,階乗を使う。
• 典型的には動的計画法。
• 実は制約的に、全探索しても間に合うかも。
• ナップサック問題　(0/1問題)
• n個の要素がそれぞれ使う、使わないを選んで、その組み合わせの中で最適なものを答える。
• 選ぶ方法とすると、ビットフラグを作って各ビットの1,0を見る方法（計算コストが低いのでできればこちら）や深さ優先探索などがある。
• nが少ないと深さ優先探索（全探索）できるが、多い時は動的計画法、動的計画法でもきつい場合は、半分全列挙などを考える。
• （競技プログラミング以外では、一般的には最適解は出せない）
• 最短経路問題
• 迷路などを解く（1ステップが1コスト）→幅優先探索
• 移動にコストがかかる（コストがバラバラ）→ダイクストラ法
• 任意の場所から始めて、一番遠い場所→ワーシャル-フロイド法
• グラフ問題
• 島検出→深さ優先探索でもできるかもですが、幅優先探索が無難
• 閉路検出→幅優先探索
• グループの検出→　union-find
• ゲーム
• 決まった条件繰り返し　→　modなどで線形時間でうまく出来るかも
• 基本的にはシミュレーション、→ 動的計画法 / 深さ優先探索
• 山が幾つかあり、選んだものからなら何個でも取れて、最後をとった人が勝ち → Nim
• 連続した範囲で・・
• しゃくとり法
• 逆関数を求める
• 数学的なテクニックを使ってうまくするんでしょうね