hack.html

<title>嘘解法・誤解法対策として入れるケース</title>
<p>
    典型的な嘘解法はこちらを参照<br>
    <a href="https://wata-orz.hatenadiary.org/entry/20111218/1324226179">嘘解法のススメ</a> by wata<br>
    <br>
</p>

<p>
    以下の全てが必要というわけではなく、問題によって意味がありそうなものを入れる。
</p>

<h4><b>全般</b></h4>
<p><ul>
    <li>最大ケース・最小ケース</li>
    <li>ある変数は最大、ある変数は最小のケース</li>
    <li>答えが最大・最小になるケース</li>
        以下のような解法が落とせる
        <ul>
            <li>最大値を求める問題で答えが負になりうるにも関わらず $0$ で初期化</li>
            <li>最小値を求める問題で答えが $2\times 10^{9}$ になりうるにも関わらず $10^9$ で初期化</li>
            <li>二分探索の上限・下限を間違える</li>
        </ul>
    <li>最大に近いケース（最大ケースをエスパーして通されるのを回避）</li>
    <li>オーバーフローするケース</li>
</ul></p>

<h4><b>最適化</b></h4>
<p>複数の嘘貪欲・ヒューリスティックを組み合わせても通せないケース</p>

<h4><b>グラフ</b></h4>
<p><ul><li>木</li>
    <ul>
        <li>完全二分木</li>
        <li>パスグラフ</li>
        <li>スターグラフ</li>
        <li>スターグラフの手が長いやつ（長い直径がたくさんあるケース）</li>
        <li>平方分割木（次数の大きな頂点がたくさんあるケース）</li>
    </ul>
<li>一般</li>
    <ul>
        <li>クリーク</li>
        <li>サイクル</li>
        <li>C4が1頂点だけ共有して連なってるやつ（最短経路がたくさんあるケース）</li>
        <li>非連結</li>
    </ul>
<li>上記それぞれに少しだけ辺を加えた/減らしたもの</li>
</ul></p>

<h4><b>Union-Find</b></h4>
<p>$(1,2),(2,3),(3,4),\ldots$ を順に追加して最後に $(1,N)$ を質問するケース（再帰が深くなるケース）</p>

<h4><b>ダイクストラ</b></h4>
<p><a href="https://snuke.hatenablog.com/entry/2021/02/22/102734">ダイクストラ法のよくあるミスと落し方</a> by snuke<br></p>

<h4><b>負閉路検出</b></h4>
<p><a href="https://www.youtube.com/watch?v=KLwNUbIyHrI">要注意！ベルマンフォード法を使う際に陥りやすい「罠」</a> by AngrySadEight</p>

<h4><b>最大流</b></h4>
<p><a href="https://gist.github.com/MiSawa/47b1d99c372daffb6891662db1a2b686">バグったDinic法のhackケース</a> by Misawa<br></p>

<h4><b>DP</b></h4>
<p>初期化を間違えた解法が落ちるケース</p>

<h4><b>素因数分解や約数が関係する問題</b></h4>
<p><ul>
    <li>素数</li>
    <li>2×(N/2くらいの素数)、3×(N/3くらいの素数)、(√Nくらいの素数)×(√Nくらいの素数)</li>
    <li>素数の2乗</li>
    <li>高度合成数（約数が多いケース）</li>
    <li>$2\times 3\times 5\times 7\times\ldots$（素因子の種類が多いケース）</li>
    <li>$2^{29}, 3^{18}$ （指数が大きいケース）</li>
</ul></p>

<h4><b>離散対数問題</b></h4>
<p>法が安全素数のケース（乗法群の部分群の位数が大きなケース）</p>