ARC161 開催記

前回 (ARC157) から約 3 ヶ月で ARC の writer をやったので，また感想とか元ネタみたいな当たり障りの無い話を綴っておこうかと思います．まだ問題を見ていない方は，ぜひご覧になっていただいて，できれば 1 問でも取り組んでいただけるととても嬉しいです．（定型文）

A.  Make M

セットの中で最後に作った問題で，ARC161 なので 161 の特徴から捻り出しました．*1 前回の A 同様「割と簡単な必要十分条件をチェックするだけ」みたいな問題になって程良かったかなと思います．が，ちゃんと証明するのは意外と簡単ではなく，今回はセットを通してそういう問題で構成されていたので，そういう意味でもちょうど良い問題だったかなと思っています．以下の問題と考えることが似ているという説もあります．

N = 1 のケースが割とネックだったようで，以下のように書くか，そもそも除いておいた方が親切だったかなと思いました．

B.  Exactly Three Bits

最後から二番目に作った問題で，これも 161 の特徴から作りました．提案時は A (300) のつもりだったのですが，「 B (400) じゃないか？」と言われてそうなりました．公式解説の 2 が想定解のつもりで提案したのですが，「 1 が簡単では？」と言われて目から鱗でした．contestant の感想でも散見されましたが，実は writer も同じ感想を抱いていたという裏話です．

C.  Dyed by Majority (Odd Tree)

このセット唯一（？）の実装問です．直観的に自然な方法をやるだけですが，細部をちゃんと実装して合わせるのが地味に大変かもしれません．元ネタは分散計算モデルにおける合意形成（こちらなど）です．問題 E とセットでの出題ですが，他にも色々候補はありました．たとえば「 K \ (\le 10^9) 回操作した後の状態を出力せよ」みたいなものも考えたのですが，閉路ぐらいでしか解けなかったので諦めました．

D.  Everywhere is Sparser than Whole (Construction)

エスパーかつ証明 AC しやすい問題でしたが，ここまで C と逆転するとは思っていませんでした．初動でだいぶ差が付いてしまったので，こちらに取り組んだ人が多かったのかもしれません．厳密に証明するはそんなに簡単ではない（と思う）ので，当初は 700 点提案でしたが，さすがに過大っぽいということで 600 点に下げて，最終的に 500 点（ C と同じ）まで下がりました．admin & tester の皆様，ありがとうございます．

公式解説が文章だけで分かりづらい場合は，サーバルさんが描いてくれた図を見るとよいかもしれません．ありがとうございます．

また，別の方針で示す方が楽という説もあります．

E.  Not Dyed by Majority (Cubic Graph)

今回の自信作＆問題児です．問題 C とともに変種を色々考えていて，「次数 3 なら 2-SAT で解けるなあ」と思い，テストケースを作ろうと実験してみたら…という感じでできました．ジャッジの方法をそのまま出題するのに比べて程良い迷彩になっていて，良い難易度になったのではないかと思います．提案時に「信じる心が試される」というコメントをもらったのが面白かったです．

しかし解説をちゃんと書くのがとても大変でした．公式解説の補足まで全部読んだ人は誰もいないのでは？という気もしていますが，慣れない計算を頑張ったので自分のリハビリにもなりました．Chernoff bound とか触ったの何年ぶりだろう…．このセット全体の準備時間の半分以上をこの問題の解説（証明を考えるところから書き上げるまで）に使ったと思います．*2

F.  Everywhere is Sparser than Whole (Judge)

専門分野からの布教問題です．DM 分解 (Dulmage‒Mendelsohn decomposition) の気持ちに通じているか，最密部分グラフ問題が最大流で解けることを知っているかすれば，それなりに一本道なんじゃないかなと思います．最密部分グラフそのままだと面白みが無いので，ちょっと捻ろうと考えていたら生まれました．順番としては，問題 D の方が後（「問題 F をジャッジとする問題も出題できるな？」と思ったという流れ）になります．

tester の tatyam さんに次数貪欲の近似解法で AC されたので，それ（＋乱択）を落とすようなケースを追加したつもりだったのですが，自分の乱択が不十分で結構突破されてしまいました．これは残念…．後に carrot46 さんから撃墜ケースを教えていただき，after_contest として追加したので，嘘貪欲で通した人はぜひ WA になってみてください．

まとめ

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

開始前の writer 予想 diff は 400-600-1400-1600-2800-3200 で，実際は 285-563-1746-1379-3136-3106 でした．今回はかなり良い線行ってたんじゃないかなと思いますが，C, D の逆転と，F の嘘貪欲を落としきれなかったのが想定外でした．

前回の最後にも載せましたが，理想は 3-4-5-6-7-8 なので，そのうちまた書いてみたいと思います．対戦よろしくお願いします！

追記

そういえば，開催が決まってから ARC160, AGC062 がありましたが，あわや黄落ちするんじゃないかとドキドキしながら出ていました．

*1:作ったのは ARC161 が決まってからですが，実はこの回で writer をやるのを狙っていました．161 という数に個人的に思い入れがあるので．

*2:ちなみに今回は英語解説の一部も自分で書きました．