撃墜

提供: MonoBook
2013年8月13日 (火) 10:44時点におけるimported>MikeCATによる版 (作成)
(差分) ← 古い版 | 最新版 (差分) | 新しい版 → (差分)
ナビゲーションに移動 検索に移動

撃墜とは、間違っているソースコードに対し、 そのソースコードが誤動作する入力を示すことでそれが間違っていることを示すことである。

主な撃墜方法[編集 | ソースを編集]

最大ケース[編集 | ソースを編集]

主にアルゴリズム効率が悪いソースコードに対し、問題で許されている最大のサイズの入力を与える。 成功すれば時間制限超過となるか、スタックオーバーフローなどで実行時エラーになると考えられる。

コーナーケース[編集 | ソースを編集]

主に場合分けが甘いソースコードやオーバーフローするソースコードに対し、その欠点を突くようなテストケースを与える。 成功すれば誤答となるか、実行時エラー、無限ループによる時間制限超過などになると考えられる。

適当なケース[編集 | ソースを編集]

主に適当な定数や乱数を出力するだけのソースコードに対し、なんでもいいから適当な入力を与える。 おそらく誤答となって落ちるであろうが、出力している値が問題の出力として有効な場合、 その値に対応していない入力を与えないと撃墜失敗となるので注意が必要である。

TopCoderにおける撃墜[編集 | ソースを編集]

TopCoder SRMにおいては、ソースコードを書いて問題を解くCoding Phaseの後にChallenge Phaseがあり、 ここで同じ部屋の他の参加者のソースコードに対する撃墜を狙う。

表示されている得点をダブルクリックしてソースコードを閲覧し、間違っていると感じたら 左下のChallengeボタンを押す。 ダイアログにそのコードが誤動作すると思われる入力データを入力し、確定する。

与えた入力データで本当にそのコードが誤動作すれば自分に50点が入り相手のそのコードは0点になるが、 誤動作しなければ自分に-25点される。 大量に失点するとレーティングが一気に数百減ることがあるので、注意が必要である。

また、TopCoderでは練習モードでも撃墜をすることができ、得点も入る。 練習では全員のコードを対象に撃墜をすることができるので、撃墜点だけで1位になることも可能である。

Codeforcesにおける撃墜[編集 | ソースを編集]

Codeforcesにおいては、コーディングの時間と撃墜の時間が区別されない。

まず問題を解くためのコードを書き、提出する。 提出するとPretestと呼ばれる簡単なテストケースでのテストが行われ、 それに通ると問題をLockできるようになる。

問題をLockすると、それ以降その問題に対しソースコードを提出できなくなり、 その代わり他の参加者のその問題のコードに対し「Hack」と呼ばれる撃墜をすることができるようになる。

Hackにおいては、まずソースコードを閲覧し、 間違っていると感じたら、誤動作すると思われる入力データもしくは入力データを出力するプログラムを提出する。 そのデータで本当にそのソースコードが誤動作すれば自分に100点が入り相手のそのコードは0点になるが、 誤動作しなければ自分に-50点される。

TopCoderと違い、練習でHackをすることはできないと考えられている。

その他の撃墜[編集 | ソースを編集]

バグ報告として対象のプログラムが誤動作する例を示すことがあるが、これも撃墜と考えられる。

ここにDXライブラリの掲示板に上げられた撃墜の例を示す。