競技プログラミングでバグった時のためのチェックリスト
初めに
簡単な問題例について手元で動作させてみたか？（検証で重要） 途中経過が残っていることが望ましい。
自分が予想だにしていない要因がバグの原因になることを防ぐため。
要素の個数・長さを回答に使う時は、それを定理として正しく証明したか？
各論
数値演算
int64_tの演算に対して、リテラルにllをつけているか？
先頭にusing std::abs;
変数の初期化する位置は適切か？（特にループ内・ループ外）
存在しない場合、SEGVを起こす可能性がある。
ループ変数についてはその上に自然言語による定義を明確に記述した上で、実装に取り組む
forループから変数宣言を独立させる場合には、変数初期化をループに必要か確認する
二重ループにおいて、二重にbreakできていなかった
解をチェックせずにループが終わってしまう場合が存在しないか？
初期状態が正しかった場合など
code:diff
+// フラグで管理すると、一切フラグの更新処理が走らずにforループが終わってしまったときに誤った解が出力されてしまう
- bool success = false;
for (size_t i = 0; i < 60; i++) {
+ // FIXED: ここにbreak文を入れてしまって、かつ、のちにフラグを更新するような判定コードがあるときは、初期状態が解だったときにフラグが更新されることなく処理が終わってしまう。
if (y < (1ull << i)) { break; }
if (( ((x&y) ^ a) & (1ull << i) ) != 0) {
x += (1ull << i);
y -= (1ull << i);
+ // FIXED: ここにフラグを更新するような判定コードを書いてしまうと、初期状態が解だったときに判定が行われずに処理が終わってしまう。
- if (x&y == a) { success = true; break; }
}
if ((x&y) == a) { break; }
}
+ // フラグで管理せず、直接判定しにかかった方が良い
- std::cout << (success ? "Yes" : "No") << std::endl;
+ std::cout << (((x&y) == a) ? "Yes" : "No") << std::endl;
系列の線形探索
ループ
系列のある区間にわたって操作を行った時、端にあたる要素が必ず存在することを暗に仮定していないか？
すなわち、任意の区間$ A_i, A_{i+1} \cdots, A_jに対して$ A_{i-1}や$ A_{j+1}が存在することを暗に仮定していないか？
あるいは、区間の長さが0の場合はないか？
1ull << iが適切ではないか？
データ構造
begin(), rbegin()などで大きい要素や小さい要素要素を取ることができるが、一番目二番目に大きい・小さい要素は存在するか？