yukicoder contest 355 - yukicoder が 2022/08/05 に開催されました。参加してくださった方、ありがとうございました。
時間があれば全体の開催記を書きますが、今回はC問題で発生した出題不備について書こうと思います。 C問題 No.2029 Swap Min Max Min - yukicoder のネタバレを含みます。
初めに、C問題の不備によって混乱させてしまったことに対しお詫び申し上げます。この件については、Writerである私に責任があると考えています。申し訳ございませんでした。
次に、コンテスト中に Clar で指摘していただいた maspy さん、 SSRS さん、 Nyaan さん(Clarの時系列順に並べています)にお礼を申し上げます。本当にありがとうございました。参加者としてはジャッジが壊れていると推測するのは非常に難しいと思いますが、少しでもおかしいと思った場合はすぐにClarを投げていただくと、出題側は非常に助かります。特に今回はACが多数出ていてコンテスト中にも気づかなかったので、本当に助かりました。
また、リジャッジ後にKazunさんにもClarで順位表更新方法を教えていただきました。ありがとうございました。(yukicoderの順位表では、WA → AC の変化が正しく表示されていなかったようです。現在は修正されています。)
以降で、何が起こったかの説明と、現在考えている解決策を書こうと思います。
時系列
コンテスト前 yukicoder 355 のC問題において、実際には最適でない解を最適解としてケースを作成していた
21:50 ごろ Clar により指摘を頂く。Y.Y.さんと相談し、修正を行う
22:00 C問題のClarに、この問題に不備がある旨の通知を行う。この時は修正はコンテスト後に行おうと考えていたので、その旨をC問題の問題文に追記
22:15 Y.Y.さんが正しい解答を書く。相談の結果、コンテスト後ではなくすぐ修正をして、チャレンジしてもらおうということに
22:30 Shirotsume が書いた解答とY.Y.さんの解答が合わない。ここで、Y.Y.さん、maspy さん、SSRS さんの解答が一致することが確認できたため、テストケースを差し替えてリジャッジする
22:40 Clar でリジャッジを行ったとアナウンスする
23:10 Shirotsume の解答が合う
23:20 コンテスト終了
どのような不備があったのか
が偶数のケースでは、この問題は 個の と 個の からなる数列を、 どうしが連続しないように並べ替えるための最小 swap 回数を数える問題となる。 これを解く際に、 と のケースの 種類だけであると勘違いし、 のようなケースを考慮していなかった。 結果、最適でない解を想定解としていた。
どのように対策するか
このような論証漏れに対する最も有効な対策は、maspyさんもtweetで指摘しておられたように、愚直解を書いて比較することだと考えています。
愚直解が十分書きやすい場合、可能ならば小さい場合の愚直解を書いておくと、ミスる確率が結構減らせるはず。
— maspy (@maspy_stars) 2022年8月5日
同コンテストの問題(FやG問題)では愚直解を書いていましたが、この問題は愚直が書きにくいことや、コンテスト中でも難易度設定が低めであることなどからそれを怠っていました。
このコンテストでは、解説をしっかり書くことを目標にしており、できるだけ論理の抜けがないよう注意しました。そのため、この解説は間違っていないだろうという自信を持っていました。今回はそれも裏目に出たと思います。
自分で書いた解説から論理の抜けを指摘することは、自分の思いつかなかったことを見つける必要があり、かなり難しいです。testerにとっても、解説を読むとそれが正しいものだと思ってしまうので指摘は難しいと思います。TLEなどと違い、hackケースを見つけることも困難なので、可能な限り愚直など機械的な方法で判定するべきだと思います。
writerをするときだけではなく、testerをする際もできる限り愚直を書くべきだと思います。
今回はありませんでしたが他の不備として入力形式やジャッジ不具合等も考えられます。これらについてもtesterがチェックしておく必要があると思います。
実際に不備があった場合、どうするべきか
今回はyukicoder等有志コンテストについて書きます。AtCoderなどでは話が変わってくると思います。
コンテスト中に不備があった場合、その問題を即修正すべきかどうか悩みましたが、私はできる限り早く修正して、参加者に取り組んでもらうべきだと考えました。yukicoderはレート等がかかっているわけではなく、純粋に楽しみで参加してくださっている方が多い印象があります。そのような方に最も楽しんでいただくためには、単に取り下げるより、修正して再度仕切り直した方がよいと思いました。今回は修正解が早く用意できましたが、そうでない場合は取り下げ等考える必要があると思います。
おわりに
今回の不備について、改めてお詫び申し上げます。現在はC問題も修正されており、正しいジャッジが行われるようになっています。解法が面白い問題なので、ぜひ取り組んでみて下さい。他の問題についても、良い問題をそろえられたと思いますので、ぜひ解いてください。また、testerをしていただいたとりゐさん、Y.Y.さんに、改めてお礼申し上げます。ありがとうございました。
この件で作問やtesterに対して「大変そう…」という印象を持たれた方もいるかもしれません。確かに今回はかなり大変でしたが、作問/testerはとても楽しいです。ぜひ積極的にやってみることをお勧めします。その際は、解説を批判的に読む、愚直解を書くなどして、できるだけこのようなことを起こさないように頑張ってください。
私は今回のコンテストで持っている原案をほぼ全部出してしまったのでもう残っていないのですが、また溜まってきたら開催したいと思っています。その際はよろしくお願いします。