クマーの競プロ精進日記

AtCoder赤とICPC World Final目指して頑張ります．競プロ自戦記、アルゴリズムなどについて

ARC 175 開催記 (Kite_kuma 視点)

昨日の記事でも書いた通り，ARC175 の writer をやった．この 3 人でのコンテスト開催というのはずっと前からチーム内で言われていた野望の一つであり，しかもそれが自分にとって一番愛着のあるコンテストである ARC として開催できたことがとても嬉しい．今年度の ICPC でも結構良い結果を出せたし，もう本当にこのチームで思い残すことはないかもしれない．

準備期間

チーム SPJ の Discord サーバで，私がそろそろ ARC やらね？と言い始めたことが開催のきっかけだった．

よく考えると (考えなくても) 作問経験が豊富で，ARC の単独 writer も何度かやっている nok0 に比べたら，作問を頑張る必要があるのは私の方だった．

このやり取りをきっかけに適当に問題を考え始めた．個人的なこだわりとして，競プロは数え上げではなく最適化こそが至高だと思っているので，最適化問題，それも自分が好きな文字列アルゴリズムが絡みそうなものを考えた．そうしてできたのが F 問題である．当初これは E だと思っていたのだが，それよりはかなり難しいという話になって F に置くことになった．

F について

しばらくして zkou が E, nok0 が D を提案してくれて，このあたりでほぼ開催する流れになっていた．このあたりで，A-C の問題タイトルの頭文字を S, P, J にしてやろうぜという話になった．

これみんな気付いた？

A-C も各自で適当に生やして，6 問の原案が揃って開催準備が始まった．たくさん問題を考えて疲れたので，癒しを求めて (？) チームで箱根旅行に行った．

大涌谷からの景色

美味い飯と温泉で気分が最高になった後にホテルの部屋で問題文の校正をしたりした．珍しいタイプの競プロ合宿だと思う．めっちゃ楽しかった．writer 料で行く旅行，最高なのでおすすめです．

問題所感

ここからは各問題の所感について述べていく．解法のネタバレをたくさん含みます．

A

zkou 作．たぶんこれが一番最後にできた問題．原題ではスプーンを取るルールは今の問題と同じだったが，以下のように求める対象が少し異なっていた．

N 人の利き手の完全な情報が与えられる．人がスプーンを取る順序 N! 通りのうち，全員がスプーンを取るものの数を \bmod 998244353 で求めよ．

これだと 500 点くらいだと言われていたが，A にしては難しすぎるということで今の問題になった．原題の方が綺麗な問題なのでもったいない気持ちがあったのだが，今見ると問題文の読解コストも大きいので ARC-A としては今の問題の方が良いのだろうと思う．良ければこちらも解いてみて貰えると嬉しい．

実際のコンテストでは clar がたくさん来た．競プロ界隈ではやや珍しい言い回しも多かったせい？これでも問題文めっちゃ頑張ったので，すいません…．

余談だが，先日行われた UTPC2023 にこの問題があったら迷わず原題のまま採用されていたと思うので，admin って難易度調整のために大事なんだなあと思ったりした．

B

nok0 作．A でも B でも使えるように，swap と parenthesis で問題を作ったらしい．作問に慣れてるねえ．

内容は特にどうということはない最適化問題である．括弧の swap を置換 2 回でできることにうっかりしなければ大丈夫だと思う．サンプル 3 は 3 人のレート由来．(zkou もっとレート上げろ！)

A が難読だったせいか，AC 数はこちらの方が多くなった．

C

私作．nok0 が適当に思いついて解けなかった原案に対し，私が大幅な改変を行ってほぼ別問題になった．当初は差の絶対値の和を最小化するだけで考えていたが，あまりに自明すぎるので辞書順最小を追加したら，まあまあ非自明で ARC-C に置けそうな問題になった．

自分の解法がとても説明しづらかったので解説を書くのに難航したが，admin の解法がアルゴリズムも証明も非常に明快だったのでそれで解説を書いた．

余談だが，J から始まる問題名がなかなか思い浮かばず，危うく問題名が "Just Optimize it" になるところだった (ひどすぎる)．あと，サンプルテストケース 2 は，「2024 年 3 月 24 日 ARC175」から．

ここまでは前座で，ここからの 3 問は面白さに自信のある問題たちである．…と思っていたのだが，この C も詰まった人がかなり多かったようだ．まあ確かに方針で外れを引くときついか．

D

nok0 作．元ネタは LIS on Tree という，私が競プロ初級者のころに開催された ABC の問題である．これはこれで初級者に良い問題だと思うが，今回の D 問題はそれの構築版と言える．

部分和問題に帰着されるのは問題を開いてすぐ分かるのだが，そこから私は 20 分以上悩んだ．単なる貪欲アルゴリズムで解けることに気付くと非常に気持ちが良い．とりあえず重みの降順で貪欲やって投げてみよう，とするだけで通ってしまうので，人によって向き不向きの分かれそうな問題だと思う．

また問題の性質上，マラソンのような解法を落とすのは難しい．以下の問題に登場する乱択アルゴリズムを少ない回数試すだけで，ランダムに作成したケースのほとんどに正解できる．

問題: LIS on Tree 2 の部分和問題パートについて，以下の乱択アルゴリズムが正当な出力を行う確率が O(1/N) であるような入力を 1 つ与えよ．

  • 頂点 1 以外の重みが 2 以上の頂点をランダムな順序に並べ替え，その後ろに重み 1 の頂点を並べる．その順序で，重さが K-N 以下ならば追加する貪欲アルゴリズムを行う．

ただ，こういった方法を試す人は大抵重みの降順ソートくらいは試すだろうから，出題側としてはある程度諦めている面はある．

E

我らが天才・zkou の面目躍如である．私も nok0 も，これを自力では解けなかった．3 つ組に分けるのは思いつくのだが，そこからが全く進まず，そもそも K = N^{2} のときですら作れないが…？と思って解説を見たら，

たとえば x+y+z \equiv 0 \bmod N を満たす点集合を取ると条件を満たす．

と書いてあって，は？いや確かに…となる．皆さん，こいつの頭の良さを分かって頂けましたか？zkou にとってはこれ自明らしいです．本番で時間内に思いついた人はすごい．

これを思いついてからのステップもそれほど自明ではないので良い構築問題だと思う．zkou の問題は問題も解法もとても美しい．UTPC2022-D もおすすめです．

F

私の渾身の作問である．可変長列の集合における辞書式順序には以前から興味を持っていた．順序体の公理には a \leq b \Rightarrow a + c \leq b+c があるのだが，この + を文字列の結合演算， \leq を辞書式順序としてみなすと，この性質は成り立たないことが分かる．この反例について考えていたら，解説の補題 2 を示すことができた．

また，文字列の無限回の繰り返しどうしの辞書順比較については以前教えてもらったことがある．*1

この議論だと LCP が一致することまでは分からないので，そういったところを詰めて補題 1 ができた．そして，これら 2 つの補題を生かせるような最適化問題を考えた．原題はもっと解法が分かりやすいものだったのだが，もう少し難しくしても解けることに気付いて今の形になった．問題文がシンプルで，とても気に入っている問題である．

最後の問題ということで，サンプルで少し遊んだ．サンプル 2 はチームメイトの名前を書こうとしたら，"nok0" が制約違反だったので，"0" だけ出力に移動してもらった．サンプル 3 は "arc" だけで 175 を作って，"ARC175" にちなんだつもりである．(答えがこれになるまでランダムな入力を作った)

本番は 0 AC．なんでだよ．みんなむずすぎてごめん．でも問題綺麗だから是非一読してほしい．解説も頑張って書いたから補題のところだけでも読んで欲しい．

作問に対する感想

競プロは自分で問題を作っても自分からすれば自明でつまらないし，他人の作った問題を解く方が面白い．これまではそう考えていたのだが，ここ 1 年くらいでその考えも少し変わったように思う．

確かに競プロを始めてすぐの頃は問題を解くだけで満足できていたのだが，何年か続けて知識が付くうちに新鮮さが失われ，少しマンネリ感を覚えるようになっていた．競プロは将棋や麻雀と比べると，競技の中で直接人*2と関わることが非常に少ないゲームであり，上級者どうしの交流がゲームの大きな醍醐味の 1 つだと考えている私からするとやや物足りなさを感じるところがあった．

そんなことを思っていた折に，チームメイトに誘われて UTPC2022 の運営の手伝いをやってみたところ，これが意外と面白かった．私は B, C 問題の writer を担当したのだが，思っていた以上に非自明な問題ができたし，参加者がそれについて感想を述べてくれるのがとても嬉しかった．他の場所で他のプレイヤーと関わる上での話題にもなった．

このときの経験から少しだけ作問のことに気をとめるようになった．チームメイトの協力のおかげで，ARC を開催することができた．特に writer 経験者である nok0 には非常に助けられた．

ARC は EF 問題に求められる質が高く，一人で全問作り上げるのはかなりしんどいと思う．今回のように橙以上の何人かで結託すれば作問の負担も軽減されるので，他の人たちも是非やって，もっと Rated コンテストを供給してくれると嬉しい*3．

最後になりましたが，このような機会を下さった AtCoder 社の皆様，ご参加いただいた皆様，ありがとうございました．またいつか，問題が生えたらやります．

*1:ここに書いてある証明がかなり面白い．このことを忘れていて，F の解説にある証明はかなり地道な感じでやってしまった．

*2:チームメイト除く

*3:特に，強い ICPC のチームとか，大学コンで芸術的な問題を披露してる人とか