嘘解法・誤解法対策として入れるケース
Latest Author yuki2006 /Date 2024-06-01 00:11:35 / Views 333
典型的な嘘解法はこちらを参照
嘘解法のススメ by wata
以下の全てが必要というわけではなく、問題によって意味がありそうなものを入れる。
全般
- 最大ケース・最小ケース
- ある変数は最大、ある変数は最小のケース
- 答えが最大・最小になるケース 以下のような解法が落とせる
- 最大値を求める問題で答えが負になりうるにも関わらず $0$ で初期化
- 最小値を求める問題で答えが $2\times 10^{9}$ になりうるにも関わらず $10^9$ で初期化
- 二分探索の上限・下限を間違える
- 最大に近いケース(最大ケースをエスパーして通されるのを回避)
- オーバーフローするケース
最適化
複数の嘘貪欲・ヒューリスティックを組み合わせても通せないケース
グラフ
- 木
- 完全二分木
- パスグラフ
- スターグラフ
- スターグラフの手が長いやつ(長い直径がたくさんあるケース)
- 平方分割木(次数の大きな頂点がたくさんあるケース)
- 一般
- クリーク
- サイクル
- C4が1頂点だけ共有して連なってるやつ(最短経路がたくさんあるケース)
- 非連結
- 上記それぞれに少しだけ辺を加えた/減らしたもの
Union-Find
$(1,2),(2,3),(3,4),\ldots$ を順に追加して最後に $(1,N)$ を質問するケース(再帰が深くなるケース)
ダイクストラ
ダイクストラ法のよくあるミスと落し方 by snuke
負閉路検出
要注意!ベルマンフォード法を使う際に陥りやすい「罠」 by AngrySadEight
最大流
バグったDinic法のhackケース by Misawa
DP
初期化を間違えた解法が落ちるケース
素因数分解や約数が関係する問題
- 素数
- 2×(N/2くらいの素数)、3×(N/3くらいの素数)、(√Nくらいの素数)×(√Nくらいの素数)
- 素数の2乗
- 高度合成数(約数が多いケース)
- $2\times 3\times 5\times 7\times\ldots$(素因子の種類が多いケース)
- $2^{29}, 3^{18}$ (指数が大きいケース)
離散対数問題
法が安全素数のケース(乗法群の部分群の位数が大きなケース)