yukicoder 423-426 作問記録 - はむこのブログ

投稿型プログラミングコンテストであるyukicoderで、僕が作った4問でコンテストが開かれた。yukicoderは最近勢いのあるコンテスト基盤で、気軽に皆が問題を投稿できることが特徴である。16世紀のルネサンスのような、問題を出し合って解き合う雰囲気が楽しい。作問時のyukicoderの管理人とテスターとのやりとりは、自分の勉強にもなった。

作問の流れは、以下のようになっている。

問題を作る
テスト入力を作る
解説を書く
テスターと呼ばれる人とやりとりし、問題が正しく作られていることを確認する。問題のより良い解法を一緒に模索する。
実際に問題を出す
コンテスト中の質問に答える
最終的な問題の不備を修正する

作問の練習用に、AからCまではやるだけという感じの問題を作った。D問題は自分で作っておきながら難しすぎたので、らてさんと相談しながら ${O(\sqrt{n})}$ 解を実装した。のちに、りあんさんと相談していたら ${O(\log n})$ 解が爆誕した。

テスターとのやりとりが非常に勉強になった。

C問題では難易度見積もりでテスターと議論があった。僕の難易度見積もりは★2だったのだが、確率問題なので★3とした。一方、テスターのbtkさんは数学的厳密解を出そうとしたために★4と見積もった。このテスター解（確率を行列演算で求める方法）が面白かったのだが、制約がキツいので誤差の問題でこれが通らない。テスター解を通すために、制約を緩和したのだが、それでも通らなかったのでテスター解を想定解とするのを諦めた。

D問題では、想定解は平方分割で ${O(\sqrt{n})}$ 解法だったが、テスターのりあんさんが $O(\log n)$ 解を出してくれた。これを想定解とするように制約をキツくする調整を行った。さらに、りあんさんはテストケースの追加指示・解説のミス指摘など、多くの貢献をしてくれた。考察が終わってみると実装も比較的軽く、綺麗なコードになるのでいい問題になったと思う。勉強にもなったし、いい問題になったと思うが、問題完成がコンテストの10時間前だった。

AがWA祭りになった。コーナーケースの問題を出そうとしていたから、予想していたのだが、さすがに一発ACが10%しかいないのは、問題がダメだったなあと思った。leading zerosの厳密な定義を書いていなかったのもよくなかった。

Dはコンテスト中に★4から★5に格上げされた。★4にしたのは、解答を聞いてみればただのsegment treeなのと、この解答を出してくれたテスターが黄色だったから。黄色上位なら解けるだろうと思っていた。甘かった。実際には、btkさんと、LGMレベルのantaとyosupoさんの3人しかコンテスト中に解けなかった。

Dの非想定解 ${O(q^2})$ が出た。初期値が単位行列であることと、クエリ数が小さいので疎であることを利用した解答だった。やはり作問には自分のアルゴリズム力が重要であることを再確認した。

Dのリアクティブの設定が上手く言っていなかった。コンテスト後に管理人に指摘され、リアクティブを問題文から消す羽目になった。クエリ先読みしても大して解法が増えなそうだったので、コンテスト後に問題文から全削除した。

D問題の解説が間違っており、数人の時間を無駄にした。数学的にきちんと書いたつもりだったが、一箇所添字が間違っていた。コンテスト後、解説をそのまま忠実に実装したkmjpさんとpekempeyさんがWAを出しまくっていて申し訳なかった。

総じて、楽しくやりとりしながら作問できた上、勉強になったので良い経験だった。