ARC157 開催記

お久しぶりです，Y.Y. (@ygussany) です．競プロを始めて 3 年弱で，2 年半ほど延々と AtCoder のコンテストに contestant として出続けていた訳ですが，ついに AtCoder Regular Contest (ARC) の writer を務めることができました．ということで，感想とか元ネタみたいな当たり障りの無い話を綴っておこうかと思います．まだ問題を見ていない方は，ぜひご覧になっていただいて，できれば 1 問でも取り組んでいただけるととても嬉しいです．（定型文）

A.  XXYYX

この問題の元ネタは計算量理論のお話で，

X, Y からなる任意の有限長の文字列を入力として，「入力中文字列中の X と Y の出現回数が同じである」ことを判定する有限オートマトンは存在しないが，「入力文字列中の XY と YX の出現回数が同じである」ことを判定する有限オートマトンは存在する

というものです．直観的には，前者は文字列の途中でいくらでも離れてしまい得るので，入力以前に状態数が固定されるような機械だと認識できないが，後者だと常に 0, \pm 1 の値しか取らないので，有限状態でも記憶できて正しく認識できる，というお話になります．

まさにこの事実が肝になっている問題ですが， B = C = 0 がコーナーケースとなっていて，引っ掛かってしまった方も多いのではないでしょうか？私も引っ掛かりました． N の制約が小さめなのはわざとで，その方が問題として面白いかなと思っています．

B.  XYYYX

一番最初にできた問題で，設定も解法もシンプルな割に，地味に実装が重めで，コーナーケースも凶悪で，とても気に入っています．もちろん私もコーナーケースに引っ掛かりました．

最初は A (400) で提案したのですが，B (500) になって適切だったかと思います．admin, tester の皆様ありがとうございます．操作回数を K 回以下として簡単にするのもアリかなと思いましたが，最初に全部反転するの賢いなと思ったのでそのままにしました．

C.  YY Square

ド典型枠のつもりで 500 点提案だったのですが，これも tester さんのおかげで 600 点になりました．ありがとうございます．問題としては，B と D から間に置けそうな変種を設定から作ったという感じで，あまり言うことはありません

D.  YY Garden

今回のセットで一番気に入っている問題です．「こんなの解けたら面白いな～」とぼんやり考えていたら解けた，という感じでした．600 点提案で特に誰も 700 点以上を主張しなかったので 600 点据え置きになりましたが，前が上がったので 700 点でも良かったのかもしれません．意外と C と大きく離れて驚きました．

計算量の見積りが少し力尽く気味なのと，テストケースをちゃんと作るのがなかなか大変でした．「行と列の必要条件しかチェックしていない」ものを落とすケースはそれなりに入れているのですが，区画の条件がダメなときは割といたるところでダメになっていることが多いので，部分的にでもチェックしているようなコードは落とせませんでした．以下のようなケースを入れると改善できるようです．のいみさんありがとうございます．

E.  XXYX Binary Tree

もちろん A とセットで考えた問題です．最初は YY も入れて形にしようとしたのですが，完全二分木にしてもよく分からなかったのでこの形に落ち着きました．条件を整理すると割と典型的な二乗の木 DP になるので，700 点で妥当だと思っていますが，D までで時間を取られて十分に取り組めなかった方が多いかもしれません．葉に書き込む Y の個数をキーにすれば \displaystyle\frac{N}{2} 以下になるので妥当だろうという気持ちで \sum N \le 10^4 にしましたが， \sum N \le 10^5 と見間違えたという方も何人かいるようなので， \sum N \le 8000 とかにするのが良かったのかもしれません．

余談ですが，前回の writer の nok0 さんのコメントにとても共感しました．

F.  XY Ladder LCS

ボス問です．最初は N \le 2000 とかで解ける問題なのでは？と思って考え始めたのですが，あまりにも不可能でした．答えの下界を観察して DP に繋げるというのが推しポイントで，これも気に入っています．想定解法は UNISON SQUARE GARDEN のライブ中に突然思い付きました．800 点提案でしたが，tester さんの活躍により 900 点に上がり，妥当なところに落ち着いたように見えます．重ねてありがとうございます．

まとめ

まず，admin の maroonrk さん，tester の maspy さんと Nyaan さん，翻訳の evima さんには準備段階から大変お世話になりました．ありがとうございます．

開始前の writer 予想 diff は 400-1100-1500-1900-2200-3000 だったのですが，実際は 348-1529-1802-2435-2877-3517 でした．B 以降を全部 1～1.5 色ぐらい下に見ていて，マジか…と反省しています．とはいえ，傾斜としてはまぁまぁ良い感じになったのではないかなと思っています．*1

yukicoder でコンテストを開いてから 1 年半ほど経っていますが，やはり単独 writer コンテストは楽しいですね．これからも良い問題・コンテストを作っていければと思っているので，引き続き対戦よろしくお願いします！

*1:A と B の間にもう 1 問欲しいですね…