はじめまして
Atcoder Regular Contest 141 で writer をやらせていただいた chinerist です。 yukicoder などで何回か出題や単独コンなど開いていましたがついに ARC の writer をすることができました！
この記事では出題した問題がどのようにして作問されたかなどの作問裏話を紹介していきたいと思います。問題に関するネタバレを含むかもしれないので注意。
作問の経緯
- A問題
作問したことがあるとわかると思いますが、簡単で面白い問題（かつ既出でない問題）をつくるのは結構難しいです。はじめは ARC141 ということで回分数を題材に作問しようとしたのですが、回文の処理ということで難しい問題だらけになってしまいました。結局1週間前まで粘りましたが思いつかなかったので回文→周期的な数に変えて出題しました。ちょうどコーナーケースもあるし。
- B問題
数え上げの問題出したいな～と思い、「XOR」「増加列」のワードを適当に組み合わせて考えてみたところ、いい感じのギャグになったので出題しました。6問の中では作問にかけた時間が一番少ないです。
- C問題
（難易度めちゃくちゃ外してしまいました。DEFが赤diffやら金diffになった元凶はこの問題だと思います。参加者の皆さん、ごめんなさい…）
お気に入り枠です。原案は
順列
が与えられる。長さ
の文字列
であって、
、
がいずれも「正しい括弧列」になるものを構築してください。
という問題でした。 で解けます。
ただ本質がまあまあくだらないのでどうにか改造できないかなと思い、まず「正しい括弧列」 から
が「正しい括弧列」になる
を求める問題にしました。次に、これをひっくり返して「辞書式順序最大の
から
を求めろ」という問題にしました。
この段階でもういいかなと思いテストケースを作り始めますが、なぜか が成り立つような自明なケースしか作れません。このわけを考えたところで問題の本質に当たる部分が思いつきました。このままだとギャグ問にしてもお粗末なので
が一般のケースでも同じように解けることを確認して出題しました。
こういう風に答えから作った問題だと難易度評価外しがちですね…
- D問題
お気に入り枠です2
競プロで約数・倍数に関する問題を解いているとたまに入力が「良い集合」のときだけを考えればいいことがありますが、僕は「良い集合のサイズは実は小さいので解けるのでは？」と勘違いするのを100回ぐらいやりました。もちろん要素の最大値が のときは
で「良い集合」を作れてしまうので特に小さくはなりません。
さて、こういう反例を考えると「良い集合の最大サイズは半分なのか？」ということが気になります。証明を考えてみると にわけるといい感じになります。この段階で「元の集合が
でなくても解けるのでは？」と思い考えてみると典型問題に落ちています（ビックリ）。
ただこのまままだとdilworthの定理を用いて無考察で解かれるかもしれません。これを防ぐために「すべての良い集合の和集合、積集合」あたりを求めさせるようにしました。
- E問題
この問題の作り方はB問題に近いです。たくさん頂点、辺があるグラフを考える→「(u,k),(v,k)を結ぶ」というクエリを考える→それだとつまらないのでずらしてみる→考えてみると解ける、といった感じで作問しました。
- F問題
お気に入り枠です3
競プロではたまに文字列削除の問題が出ます。例えば
や
です。この2問の大きな違いとして「どのように削除を行っても最後に残る文字列は一意か？」という点があげられます。僕は一意に定まる場合の証明をしたことがなかったのですが、AGC055Bの解説に載っていて納得できました。
さて、証明を読んだ後は「どういうケースで証明が破綻するか？」というのが気になります。一番わかりやすい例としては ABC, BCD などのように suffix と prefix が重なる二つの文字列があるとまずそうです。このような考察をするととりあえず多項式時間の解法は思いつきます。ここからさらにテストケースを作ろうと考察したときに解説の内容にたどり着けました。
結構「こんなの解けたらダメだろ」って見た目になってるし、ARCではあまり見られなかったゴリゴリの文字列問題が作れて個人的には満足です。
感想
参加してくださった皆様ありがとうございました！yukicoderでも出題はしていましたが、やはり1000人超の人に解かれたりTLで議論されるのは楽しいですね。次回はもう少し崖がないようにしたいです。
あと今回テストケース作りが結構大変でした（特に F は文字列の問題ということでTLE解法に対応するケースを考えるのが意外と難しかったです。二度と文字列問題作りたくねえ）。こういうのを体験しているとほかのwriterにも優しくなりそうです。
今度がいつになるかはわかりませんが原案がそろったらまたやりたいと思っているのでよろしくお願いします！
