嘘解法・誤解法対策として入れるケース

Latest Author yuki2006yuki2006 /Date 2024-06-01 00:11:35 / Views 333
0 (Favした一覧ページはユーザーページから)

典型的な嘘解法はこちらを参照
嘘解法のススメ 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}$ (指数が大きいケース)

離散対数問題

法が安全素数のケース(乗法群の部分群の位数が大きなケース)