pattern.html

<title>競技プログラミング問題パターン</title>

<h4 class="shadow">競技プログラミングで出てきそうな問題パターンの考察</h4>
<ul>
    <li><span>シミュレーション</span></li>
    <ul>
        <li><span>言われたとおりにシミュレーションをする。</span></li>
        <li><span>考え方を変えれば少し上手い方法があるかも。</span></li>
    </ul>
    <li>全探索</li>
    <ul>
        <li>深さ優先探索・幅優先探索、ビットフラグなど使いとりあえず全探索する。</li>
    </ul>
    <li>陽に解を検索する</li>
    <ul>
        <li>算数的・数学的にうまくできそうだけども、考え方を変えて解候補を探索する方法</li>
        <li>全体の$K$個目を求めるときなどに使えるかも。</li>
        <li>$f(x)$が単調増加する場合に、$x$自体を二分探索し、$f(x)=A$になるものを見つけるなど</li>
        <li>思いつかない事が多い（運営者は）</li>
    </ul>

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