AtCoder の公式コンテストで初めて Writer を務めました。
ARC の Writer をやるのはずっと夢だったのでとても嬉しいです。
Tester の Nyaan さん、 maspy さん、Admin の snuke さん、ありがとうございました。
経緯
レートHighest 黄色の人が ARC の writer をやるのは前例が無いと思いますが、snuke さんがDMでスカウトしてくださり、例外的に writer をやらせていただけることになりました。
snuke さんは自分が以前開催した yukicoder の単独コンに参加してコメントしてくださったり、あーだこーだーの配信で興味ある writer(?) で milkcoffee の名前を挙げてくださったりしていました。TUPC の問題も見てくださっていたみたいです。今まで作問を頑張ってきて良かったと心底思いました。
社会人になって競プロ(特にアルゴ)に割く時間が減っていたところでこのDMが来たので、狂ったように作問をしていた時期を思い出して再び作問集中期間に入りました。作問ストックは結構ありましたが、ARCに良い問題を出したい一心で頑張りました。結局、今回は A と C 以外はDMを頂いた後に作った問題です。
全体の感想
開催前は不備がないか心配でしたが、無事にコンテストを終えることができて安心しました。
気づいたら一瞬で解ける問題が多いこともあり、全完が大量発生しないかと思っていましたが、Rated の全完は 17 名だったらしく、耐えたと思います。
個人的にはもっと面白い問題を作りたかったという反省もありますが、コンテスト後の感想ツイートを見る限りある程度は満足いただけたみたいで良かったです。
各問題について
AとDがもう少し解かれて、Bがもう少し解かれないと思っていましたが、難易度傾斜は概ね予想の範囲かなという感じです。
以下、ネタバレ有り
A. Four TSP
AGC の「C4」みたいな問題を作りたくて作りました。N=4 の完全グラフのハミルトン閉路を書いてお絵描きしていたら、通らない辺が良い感じにグループ分けできることに気づいたので、これを使う問題設定にしました。
原案を考えたのは2年くらい前だった気がします。
想定解は O(K^2) ですが、 O(K) でも解けます。
B. Stones on Grid
完全に解法から考えました。つまり、「最小のサイクルを作る」というグラフ問題を、できるだけ別の設定で置き換えたものを考えて作りました。何かの問題を考えてグラフに帰着できると面白いですよね。
解法から考えたので難易度が読めなかったですが、思ったより解かれたなという印象でした。人によっては A よりも解きやすかったかも？確かに今回のコンテスト内では最も再現性を持って解ける問題かもしれません。
C. ABS Ball
このままの問題設定を考えて、それが解けたので出題しました。積の和典型を使いたくてこういう設定の問題をたくさん生んでいた気がします。FPS解法はまだ読めていないので読んでおきます。
この問題も2年前くらいの原案です。
D. Two Rooms
今回のコンテストの主役かつ問題児です。
「山登り法」を使った問題を作れたら面白いかなと思って考えた問題です。少しアルゴから離れていたことでこの発想に至れたのかもしれませんね。
山登り法とは局所解にたどり着いてしまう可能性がありますが、逆に言えば(何らかの意味で正の進展があれば)必ず局所解にはたどり着いてくれます。局所解は「これ以上進めない」という条件を満たしていると言えるので、その条件を問題の条件にしてしまえば、山登りをアルゴでも出題できると考えました。
当初は500点で提案しましたが、色々あって 600点になりました。snukeさんが解説放送でこの問題がコンテスト最難と言っていたように、ハマった人がいるかもしれません。証明込みで AC した人は何人いるんだろう。
自分は面白いと思って出題しましたが、かなり好き嫌いが分かれそうだなと思います。自分が参加者だったら絶対に嫌ですね。adhoc 過ぎると逆にウケないというのが経験上ありますが、それでも出したくなってしまう。
E. Drop Min
このままの問題設定を考えて、それが解けたので出題しました。本人は解くのに2時間くらいかかったと思います。
内容は割と典型寄りだと思いますが、細かいところを詰めるのが辛いと思います。
F. Add Integer
元々は A_{i+2} = |Ai - A_{i+1}| という設定で何か問題を作れないかと考えていましたが、逆から見たら2パターンの遷移になることに気づき、今の問題設定にしました。
逆から見るという発想をした後の高速化パートも綺麗になって面白いと思います。自分の作った問題ではこのタイプの高速化を使うのは初めてな気がします。
終わり
というわけで幸いにして ARC writer デビューをすることができました。
競プロ引退したら作問に関する記事をまた書こうかと思いましたが、自分が使いたいのでしばらくは自分用に取っておこうと思います。
以前書いた作問方法の記事はこのブログの過去記事に載っているのでそちらもぜひ。
自分の過去の作問リストは以下から見れます。暇な時に解いてみてください。
また作問頑張ります！
