😊

競技プログラミング：バグらせた時

に公開
競技プログラミング
tech

AtCoder/Codeforcesのアルゴリズムコンテストでバグらせた時の確認表です。
随時更新しています。
戒めのためにやらかした回の記録も始めました

一覧

[超重要]問われているものを間違えていないか？

  • 制約を言えるか？
    • 10^5 or 10^9
    • 10^{12}などlong longが必要なもの
    • 1つ or 1つ以上
    • H, W \leq 2000 or H \times W \leq 2000 など
    • 初期値に多重辺があるか ABC416E
  • 入力の形式を言えるか？
    • A_i B_i式 or
      A_1 A_2 \dots A_N
      B_1 B_2 \dots B_N式
  • 言葉を正しく読んでいるか？　特に操作が複数あるときに取り違えていないか？ 定義を正確に言えるか？
    • 有向 or 無向
    • 直径 or 半径
    • 連続 or 不連続
    • 隣り合うペア or 任意のペア
    • 末尾の要素 or 任意の要素
    • ソート済み or not
    • 0は平方数 ABC324D

手癖で書き間違えていないか？

  • 半分全列挙でソートを忘れる
  • Dijkstra法でpop時のチェックを忘れる
  • セグメント木の単位元が単位元になっていない
  • 半開区間/開区間/閉区間の境界値
    • i=1..9に対するC[i]の最小値を得るため*min_element(C+1, C+9)をやってしまった
  • 添え字間違え
    • 多重ループでi,j,kあたりが入れ替わる
    • 入れ子が外れる A[B[i]] -> A[i]など
    • [i]を[0]とする(初期化の次の行あたりでやりがち)

言い換えを勘違いしていないか？

  • ABC394F "次数4以上の頂点の最大連結成分"は誤り

失敗するケースは作れないか？

  • ランダムケース with 愚直解法と一致するか？
    • そもそも愚直解法は正しいか？
  • 極端な値の時に成功するか？
  • 境界値周辺の時に成功するか？

オーバーフローの確認は十分か？

  • 10^5以下の整数を10^5回足すとき
  • 掛け算するとき

決め打ちの定数を間違えていないか？

  • 十分大きい回数ループさせて打ち切り判定をサボるとき

状態の列挙は適切な計算量か？

  • 同じ状態を重複して数える → TLE
  • ただのDFSのつもりがN!の順列全列挙になっている

out of rangeの確認は十分か？

  • 添字、順位、数など複数の配列を行き来する時
    ABC391D

文法を間違えていないか？

  • vectorが値渡しになっている
  • 優先度付きキューに違うキーを渡している
  • 識別子が被っていて違うものを見ている

場合分けは全ての場合で正しいか？

  • 例外処理した部分だけ間違っている
    • 本質と思う分岐に気を取られる ABC401D 残り0の時の処理
  • 番兵が壊れている

modは正しく取れているか？

素直にatcoder::modintを使うのが近道

  • 負になっている
  • modしてはいけない値をmodしている
    • a^nのnにmod
    • 「modの総和」を問われている時に総和にmod

エラーコードに先入観を持っていないか？

  • 範囲外参照はREになるはず→WA
  • 無限ループはTLEになるはず→MLE,RE

DPの初期条件と状態遷移は正しいか？

  • 直前の状態からコピーするべき値をコピーしていない
  • 後で遷移元として使う値に上書きしてしまう
  • 更新する範囲が足りない
  • 禁止された状態から遷移 or 禁止された遷移
    • ABC338F 負値があるので通常の最短経路のまま書くとINF-wや-d+INFの遷移をしてしまう
  • 削ってはいけない状態を削っている
  • 同じ状態に複数回遷移する
    ABC391F※貪欲
  • 数え上げから無視されるはずの初期状態が数え上げられる
    • 「空集合のパターンが1つ」で初期化すると×　空集合のパターンも数え上げ対象になり得るためバグるABC349F

「これは典型のアレ」と決めつけていないか？

  • セグメント木に囚われると死ぬ ABC355E

バグを探す時

良い方法は確立できていないが、まず簡単・頭を使わず確認できる項目を潰すのが良いと思う

  1. 解法そのものにあまり影響されないもの
    問題文の読み間違え、オーバーフロー、値渡し参照渡し
  2. 自分が書いたロジックを多少追わないといけないもの
    変数の取り違え、ソート忘れ、out of range、番兵
  3. 本質に迫るもの
    場合分けの間違い、DPの遷移、モノイド設計、

Discussion