気をつけるべきこと

随時更新

コンテスト前に唱えること

WA が出ても焦らない

未証明でも部分点や assert チェックで確認できるかも

特に、実装が大変なアルゴリズムの場合はまず確認する

満点に固執しない、時間がない or バグらせそうなら部分点から合わせる

オーバーフローに気を付ける

誤読しない

制約を見落とさない

コピペするときはちゃんと変えるべきところを変え忘れていないか要チェック

証明してから実装する

条件は漏れていないか？

手が動かなくなったら実験する

何もしないよりはまし、エスパーできるかもしれない

生半可な直感のまま実装に走らない

間違っていると時間ロス & 焦る

ちゃんと文字に起こし、証明する

ライブラリ等が使えないコンテストにおいて

まずコンパイル用のスクリプトを書く

g++ -std=gnu++17 -o ${file%.cpp} -Wall -Wextra -D_GLIBCXX_DEBUG -fsanitize=undefined -O2 $file

サンプル確認用のも書く

for f in test/*.in; do ./main <$f | diff - ${f%.in}.out; done

時間配分を考える

一問に固執しすぎない

ランダムテスト

for i in ｀seq 100｀; do ./gen >test/${i}.in; ./naive <test/${i}.out; done

その後サンプル確認用のスクリプトを回す

立ち回り

お気に入りは全部解除

ライバルが成功しているのを見ると焦って失速する

順位表で見るのは「どの問題を何人解いたか」だけ

焦らない

構築に飛びついて破滅しない

誤読しない

考察は 1 ステップずつ証明する

誤読しない

一問一問解く前に「誤読しない」と唱える

何か変だと思ったらまず誤読を疑う

制約 given な解法を考えすぎない

思い込みは厳禁

手を止めない。実験できるなら実験する。

ランダムテストを書くのをためらわない

あからさまに変な解法になったら立ち止まる

解けたと思ったら一旦落ち着いて水を飲み、考え直す

意気込みすぎない

実装

考察用紙にステップを書く

変数名は丁寧につける

急いでいるからといって短くつけるとバグらせやすい

場合わけの少ない実装を心がける

できるだけ簡単な実装方針を考える

場合分けをするとミスる

添字や条件の変え忘れ

ネストが深くなってコードが読みにくい

バグとりの箇所が多くなる

積極的に関数化

バグとりの高速化

コードの簡潔化

assert を使う

どこでバグっているのか分かりやすい

ただし, 条件をミスると正しいはずのコードが RE する

無理やりライブラリで殴らない

分量が多いと実装も大変

コードが多いだけで頭は間違えやすくなる

計算量が悪くなる

実装を始める前にある程度の実装方針を決める

コードを書きながら考えるのは遅いしバグりやすい

ちゃんと考えておかないと, ある程度実装した後に「これも実装する必要があった」「ここの考察が間違っていた」となり頭がパンクする

ループ変数は const にする

重めのアルゴリズムを使う場合、それが適用できる条件は入念に調べる。

部分点で assert つけておくなど

あるいは、それを使わない方法を考える。

同じような実装を複数回するとき、コピペは十分に注意して行う

変数名等は変え忘れていないか？

具体的な失敗集

場合分けで, 片方をもう一方にコピペしてそれをいじったら, 添字を変え忘れた

非負の値の max を取るとき初期値を 0 にしたせいでバグらせる

dp で inf を遷移に利用してオーバーフロー

勝手に対称性を仮定する

途中で負になりうる BIT で二分探索すると死ぬ (単調性を確認！)

BFS をするときに, queue にすでに入っている要素を追加して MLE

ちゃんと追加したかどうかの bool 配列を持て

数え上げの遷移を脳死でやって死ぬ ('?' を埋めるタイプの数え上げで, 使った '?' の個数が影響する場合など)

制約の小さい部分点のために小さめに設定した MAX や INF の値をそのまま満点解法で使ってバグらせる

ループ変数を途中でいじった結果, ループが回るべきところで回らずに 20 分溶かす

cerr デバッグ出力を残したせいで TLE

SCC した結果が木 or パスグラフになると思いこむ

「全ての辺からただ一本の辺がでているグラフ」という条件だけで連結だと思い込む

森で HLD する

数列が凸だと思い込む

オイラー路が存在するかどうかの判定で連結性を忘れる

vector に push_back したことによって参照がバグる

vector<bool> の罠を踏む

動的セグメント木を実装する際に、まだ作られていない頂点に対する遅延伝搬を忘れる

__builtin_ctz と __builtin_clz を混同する

セグ木の実装で push と flush を混同する

__builtin__ 系に 0 を投げる

== と >= を間違える

INF を std::numeric_limits<int>::max() そのままにしてオーバーフロー

答えの出力を cerr に投げてて WA

構築で Yes を出力し忘れる

ループの境界条件ミス

配列を使い回すときに、再度初期化しなければならないのを忘れる

メモ化再帰において、途中で引数の値を変更してしまい、バグらせる

多重辺の処理 (明記されてければ存在すると思え)

que から pop するとき、front の値を参照で受け取って use-after-free

部分永続 UF の実装で、find(u, t) を再帰で呼ばなければいけないのを忘れる

枝刈りのために入れた continue のせいで必要な処理まで飛ばしてしまう

type-alias を間違えたせいでオーバーフロー

並列二分探索やクエリの (l, r) が昇順になっているような場合において、クエリを見る順番を逆にして計算量が悪化する

入力がソート済だと思い込む

遅延セグ木で長さの情報を持たせるのを忘れて作用に失敗

ループ変数が処理内で変化してしまい、正常に走査されない

二次元累積和のミスあるある : 最右列、最下段の伝搬が正常に行われない

2n セグ木で全体取得を O(1) でやろうとして WA