内容別リスト/基本/コーナーケース - 競技プログラミング用 知識集積所

---

---

雑な説明

プログラムの内容によっては、特殊な入力のときだけ特殊動作を要求される場合がある。
もしくは、問題的には特殊ではないが、コードの都合で特殊対応が必要になる場合もある。
これらはコーナーケースと言い、きちんとケアしないと1つだけWAみたいな結果になってしまう。
このページでは、よく現れるコーナーケースについてまとめる。

コーナーケースの典型例

個数や回数などに0が絡む場合

0回操作する、0個選ぶ、条件を満たすものが0個である、1回ごとの増加量が0である、など。
これらの計算は割り算が発生することが多く、コーナーケースでゼロ除算を踏みやすい。
また、ループが1周も回らず、1周目にやることになっているはずの処理がスキップされることもある。

データサイズが0である場合

入力全体のサイズが0であることは競プロではほぼないが、「条件を満たすものを全て探して～～」などではサイズが0個であることもある。
データが空だと.front()や.back()によるアクセスが実行時エラーや未定義動作をする他、ループが1周も回らず、1周目にやることになっているはずの処理がスキップされることもある。

データサイズが1である場合

隣り合う2要素を見る、2番目に大きい値を見る、木の辺を見る、などサイズが2以上のときしかできない処理がある。
該当する値にアクセスしようとして実行時エラーする他、ループが1周も回らず、1周目にやることになっているはずの処理がスキップされることもある。

異なるはずのものが一致する場合

考察中では別々のものとして扱っていても、制約上は同じ値・同じ位置になることがある。
例えば、区間の左端と右端が同じ、始点と終点が同じ、最大値と最小値が同じ、など。
何が起こるかはコード次第だが、よく確認しないと意図しない動作になることも多い。

探索時、目的データが端にある場合

探す値が先頭や末尾にある場合、あるいは答えが最小値や最大値になる場合、境界の些細な書き間違いで論理エラーすることがある。
また、条件を満たすものが存在しない場合も確認する。
自力で書く二分探索※や三分探索※で初期値をミスったときにおかしな挙動をしがち。

その他、境界値や制約の端で何か起こる場合

制約の最小値・最大値は、コーナーケースになりやすい。
最小値は実装の前提を壊しやすく、最大値は計算量やオーバーフローの確認に役立つ。