競技プログラミング問題パターン

Latest Author yuki2006 /Date 2015-04-19 00:53:01 / Views 1867
0 (Favした一覧ページは作成中です。)

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

  • シミュレーション
    • 言われたとおりにシミュレーションをする。
    • 考え方を変えれば少し上手い方法があるかも。
  • 全探索
    • 深さ優先探索・幅優先探索、ビットフラグなど使いとりあえず全探索する。
  • 陽に解を検索する
    • 算数的・数学的にうまくできそうだけども、考え方を変えて解候補を探索する方法
    • 全体の$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
  • 連続した範囲で・・
    • しゃくとり法
  • 逆関数を求める
    • 数学的なテクニックを使ってうまくするんでしょうね