競技プログラミングでバグった時のためのチェックリスト
初めに
簡単な問題例について手元で動作させてみたか？（検証で重要）
途中経過が残っていることが望ましい。
実装の途中でsnapして変数の中身を確かめたい。
自分が予想だにしていない要因がバグの原因になることを防ぐため。
要素の個数・長さを回答に使う時は、それを定理として正しく証明したか？
各論
「プログラムを楽に近似的に証明するための手法を考えてみる」の、検証で注力する点を選ぶときに参考になるかも。
数値演算
int64_t の演算に対して、リテラルに ll をつけているか？先頭に
using std::abs; 変数の初期化する位置は適切か？（特にループ内・ループ外）
大小で比較する比較対象は存在するか？
存在しない場合、SEGVを起こす可能性がある。
ループ変数についてはその上に自然言語による定義を明確に記述した上で、実装に取り組む
forループから変数宣言を独立させる場合には、変数初期化をループに必要か確認する
二重ループにおいて、二重にbreakできていなかった
フラグ管理
解をチェックせずにループが終わってしまう場合が存在しないか？
初期状態が正しかった場合など
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() などで大きい要素や小さい要素要素を取ることができるが、一番目二番目に大きい・小さい要素は存在するか？