😊

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

2025/01/26に公開

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

一覧

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

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

問われているものを間違えていないか?

  • 制約を言えるか?
  • 入力の形式を言えるか?
  • 言葉を正しく読んでいるか?
    • 有向 or 無向
    • 直径 or 半径
    • 連続 or 不連続
    • 隣り合うペア or 任意のペア

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

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

out of rangeの確認は十分か?

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

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

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

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

  • 例外処理した部分だけ間違っている

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

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

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

  • 半分全列挙でソートを忘れる
  • Dijkstra法でpop時のチェックを忘れる
  • セグメント木の単位元が単位元になっていない

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

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

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

  • 直前の状態からコピーするべき値をコピーしていない
  • 後で遷移元として使う値に上書きしてしまう
  • ループ範囲が足りない or 多すぎる
  • 削ってはいけない状態を削っている
  • 同じ状態に複数回遷移する
    ABC391F※貪欲

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

Discussion