やりました
動機
赤になって割と時間も経ったし、 AtCoder の tester もやったし、そろそろ writer やりたいなぁと 2 月くらいに思っていると ARC167 まであと 10 回くらいだったのでこれに出すのを狙って作問を始める。
しばらくして、いい感じにセットができたので maroon さんにセットを送る。
ARC167 をしたいですと言ったら合わせてもらいました。ありがとうございます。
セットを作ったときに、正当性の確認も兼ねて、手元で AC 想定コードを後半の問題は用意していたので、直前の準備が少し楽になりました。 E のジャッジとかだるかったので、早めに書いといてよかったです。
問題の感想
A
問題名から作りました。
一見難しそうですが、お気持ちで解けるので最初の問題に。
灰 diff なのはびっくり。
B
問題文短くていいですね。
ちゃんと場合分けが必要なんですが、 $B$ をここまで大きくすれば注意してくれるだろうと思いました。
0 とか 1 とかのコーナーケースならサンプルに入れてもいいなと思うのですが、式をしっかり立てれば気づけるので、サンプルにそれを入れることはしませんでした。
C
もともとは問題文中にある問題のままだったのですが、これだと考察をほとんどせずに適当にやれば通ってしまうのではと考え、また、強いテストケースを作るのが難しいと考えたため、数え上げにしました。
自分がこの問題にしたときに一番最初に思いついたのが $O(N^{2})$ だったので、この制約にしました。
準備中に、$A$ がソートされていれば $O(N)$ でも解けることに気づいたのですが、別にそこを要求する問題ではないので据え置き。
意外と難しくなってしまって申し訳ないです。
ちなみにこの問題は初めて AtCoder のコンテストに参加したときに、50 分くらい格闘して通した結構記憶に残ってる問題です。
問題名もなんか面白いので改題するときに問題名をパクりました。
D
最初は隣接 swap のみで $M$ を求める問題だったのですが、あまりにも簡単で結構既出なので放置していたのですが、辞書順最小化をするという作問テクを知って、放置問をみてたら作問できそうとなって出来ました。
ちゃんと条件を整理できればかなり少ない実装で AC することができます。
テストケース作成が難しくて、tester の方に噓解法が落ちるケースを教えてもらってそれを元に何個かケースを追加しました。そのテストケースで落ちてる人も観測できてテストケース作りは難しいなぁと感じました。
E
この問題も思い出があって、コロナが少し収まったときに友達の家で一緒に出て眺めてピックの定理だけどわからんねみたいになってた問題です。
ピックの定理にもこの問題とは別に思い出があったため、かなり印象に残っている問題で、作問するときにこれを眺めて格子点上の問題を作ろうとなりました。
最初は任意の多角形で、中に含まれる正方形の数と面積が与えられるのでそれを構築としていたのですが、解けそうになかったので制約をどんどん狭めて解ける形に。
たくさんの $O(1)$ 解法があって実際にコンテスト直後にユーザー解説が $2$ つ書かれていて、 maroon さんからも別解を教えてもらいました。
解説に書いているのは自分が最初にできた解法で、計算量も $O(1)$ ではないのですが、他の解法でちゃんと正方形が $1$ つであることを証明できる気がしなかったので、この解法を書きました。
ちなみにこの問題を考えたおかげで ICPC 国内予選模擬の格子点の問題を FA することができました。
出題時にジャッジを書かないといけなくて必死に考えてなんとか $O(\log X)$ のジャッジを思いつくことができました。( $ X$ は座標の最大値)
これを別に出すことも考えましたが、あんまり実装が面白くないので特に問うことはしませんでした。解説にも書いてあるのでぜひ考えてみてください。
F
問題名の元ネタ。流石にこの問題名からこれを連想できる人は少ないし(そもそも F 問題を見てる人が少ないか…)気づくのが難しいと思うのですが、問題名をこれ以上加えると汚くなったのでこの問題名に。
問題は元々 $K=2$ のとき場合のみ、つまり $N$ のみが入力に与えられて、$((N-1)!)^{2}$ 通りについての「問題 potato」の答えの和を求める問題だったのですが、これでは E 問題でも簡単くらいだと感じて、Fが欲しかったので色々考えると難しく改題できました。
解法はこれも僕が思い出のある ICPC yokohama 2022 の問題にかなり近いです。式変形がやや非自明なのでマルパクリと言われることはないだろうという考えで出題しました。
ジャッジしかない...
問題文は以下の I 問題「Quiz Contest」です。
考察も実装も難しいと思うのですが、コンテスト開始から1時間もせずに AC が出てびっくり。
難しい問題は解かれず放置という悲しい結末を辿るのですが、コンテスト中 AC も出たし、コンテスト後に遅れて AC してくださってる方もいてありがたいです。
終わりに
ここまで読んでいただきありがとうございました。
参加していただいた方はありがとうございました。
そして tester をしていただいた maroon さん、maspy さん、heno239 さん、そしてevima さん、ありがとうございました。
大きな問題なく終われてよかったです。
また作問はしたいですね。来年の TTPC なのか ARC なのかわかりませんが。
ARC は多くの人に問題を解いてもらえていいのですが、Rated のコンテストで出しちゃうとどうしても負の感情を持ってしまう人が出てきてしまって、すごく申し訳ない気持ちになってしまいます。
ただ、rated は少ないため誰かが書かないといけないですね。ARC を増やせば、良い問題を AGC に回せるかもしれないので。
F を除けば実装も軽い、面白めの問題を集めて作ったつもりなので、是非 upsolve してもらえるとありがたいです。(F も面白いです)
