クマーの競プロ精進日記

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 のチームとか，大学コンで芸術的な問題を披露してる人とか

ICPC2023 Asia Yokohama Regional・Kite_kuma (チームSPJ) 視点

念願の Regional 初出場を果たしたものの，簡単な問題のバグが取れず撃沈した昨年度は本当に悔しくて，終了直後にちょっと半泣きになっていた気がする．

1 位なんて贅沢は言わないから，5 位くらいに入れたらいいな，できれば DELIAIR と Raspberry に引導を渡したいな，と今年は思っていた．

本番前

ほぼ初期状態の PC を用いる過酷な環境なので，エディタやその設定をどのようにするかの事前準備が非常に重要である．配布された iso ファイルを用いて本番とほぼ同じ仮想環境を再現し，どのような手順で構築を行うのがよいかを確認していた*1．

本番 1 週間前などは実際に大学に集まって開始直後の手順の確認を行っていた．仮想環境は動作がかなり重いので，初期状態に近い私の学科 PC で似た環境を再現して練習に用いていた．

Day 1

この日はリハーサルだけである．nok0 が駒場祭 (東大の学園祭の 1 つ) のシフトで大幅に遅刻する*2ということだったので，zkou と私の 2 人での参加だった．翌日の twitter で知ってびっくりしたのだがこんな感じだったらしい*3．

練習コンテスト開始．B がインタラクティブで，初めて用いるテストランナーに戸惑うも，clar に書いてある通りにコマンドを打つと help が表示されたので何とかなった．これ便利すぎるからこの世の全インタラクティブ問につけて欲しいんですけど．

一通り AC した後，サンプルの入出力をどうするか zkou と相談した．これまでは問題の PDF ファイルから手作業でコピペ (あるいは手打ち) をしていたのだが，問題 C のようにサンプルが多い場合にかなり面倒だった． そこで新たにダウンロードしたサンプルの zip を unzip するコマンドをテンプレートに追加した．コマンドを工夫することで思ったより手短に処理が書けたのは発見だった．

そんなこんなでリハーサルが終了した．後半はずっと暇にしていたのだが，DELIAIR は写経練習をしていたとあとから聞いてなるほどと思った．今思うとインタラクティブの扱い方をメモしておいてもよかった．なおこのリハーサルでも印刷ができるので，翌日の本番に向けて新たにライブラリや資料を追加したくなったら適宜書いて印刷することで資料を増やすことができる．

nok0 は SPJ のチーム紹介タイムにも間に合わず，結局 zkou と 2 人で適当に喋ることに．いないことを利用して nok0 について適当なことを言ったら一部の人が半笑いだった．

nok0 が到着したのは Day 1 の終了間際だった．何しに来たん？などと煽った後は，リハーサルの感触は練習と概ね大差ないこと，bash スクリプトが一部変更になったことなどを伝えた．

恐らく全チームのなかで最も遅いであろう写真撮影をした*4．3 人で肩を組んで撮ってもらった．

明日の朝は早いので，中華街に行くこともなくすぐに帰った．

Day 2

朝 7 時 10 分．眠い．昨日布団に入った瞬間に寝付けないことを察してからというもの，合計で 5 時間も寝られていない．家が横浜から若干遠いのでもうすぐ出ないといけない．来年はホテルに泊まろう，と思いつつ家を出た．

8:40 ごろには無事コーチも含めて全員が集合でき，非常にスムーズに入場できた．もってきた資料を広げて準備をする．

クリアファイルの類を使えるか確認したところ NG だったのでええっとなる．なんとか書籍に挟むなどしてライブラリの紙を立たせようとしたものの，紙を立たせることそのものに注意が入ったのでやめた*5．

開始直前には戦略について最後の確認をした．ペナルティが重いので慎重に進むこと，zkou ができるだけ多くの問題に目を通すこと，昨日唯一インタラクティブチェッカーに触った私がインタラクティブを実装することなど．

コンテスト中

キーボードのミスタイプが続き少し萎えつつも慎重にセットアップを完了する．nok0 が A を通す．その間に私は zkou から B の解法を聞き，それは嘘だったものの，すぐに別の線形解が思いついたので通す．なんとこれが FA だった．

通されている F の概要を nok0 から聞き，2 分くらいですぐ解法が浮かんだので書いて提出し，AC．続いて D を読む．反復回数が高々 9 であることを指摘してもらって無事 AC．復元が必要であることを忘れていたせいで修正にやや手間取った．ここまで 50 分くらいで，速度はまあまあだと思う．

nok0 と zkou が E を詰めている間に私は適当に後ろの方を読んでいた．K が解けそうだが，インタラクティブでめんどくさそう．H はまあなんとかなるかも．I は難しいのか簡単なのか良く分からない．G は数え上げらしいので自分が見てもどうせ意味はないだろう．

E で 1 ペナが出て，少し炎上気味になっている．nok0 が定数倍高速化をして，これで通らなかったら一旦諦める，と言って投げたら通ってほっと一安心した．

私は K の解法を考えていた．およそ 500 本の直線で大まかな x 座標を特定できるが，その後は…？と思っていたところ，孤の長さの 2 乗は制約から必ず整数になることに気付く．さらに zkou が，「1 つ隣の直線との共通部分の長さも見たら分かるんじゃ？」と言ったことで全てが解決した．二分探索をする方針に引っ張られすぎていて単純な方法を見落としてしまっていた．

K を書き始めたが，nok0 も G が解けたようなので，お互いに実装に詰まったら相手に PC を代わるような感じでやった．ほどなくして 2 つとも通った．

まだ 2 時間しか経っていないが，既に 7 完していて，もう残りが 4 問しかない．Speed Star の圧倒的速度を横目に，希望のある問題を探す．3 人で相談して，なんとなくフローっぽい H を nok0 に，閃きゲーっぽい I を zkou に，そして凸っぽい最適化の J を私に回したのが結果的にも非常に好判断だった．

10 分ほど経ったころ，zkou 先生がその天才性を遺憾なく発揮し始める．

"必要十分条件ってこれじゃない？"

............はい，そうです．何も根拠は出せませんが，あなたが全部正しいです．zkou が提示したのその条件は，私の頭にある I 問題のイメージと，何もかもがぴったりかみ合っていて，もうこれ以上証明などを考える気が起きなかった．魔法を見ているような，浮ついた気分で書き始める．ちょっとだけ実装がめんどくさいことに気付く．浮動小数点数を使うのはおそらくジャッジも全力で落としに来ているだろう．実際に hack ケースが作れそうなことも確認した．これを整数だけで処理するには…制約が小さいから愚直にやればいいのか．書く．FA．zkou 神すぎ．これだからチーム戦はやめらんねんだよな．

nok0 と zkou が H を詰めている間，私は J を考える．惜しいところまでは行くのだが，あと少しのところで計算量が落ちない．nok0 は H の方針が詰まったようなので，フローの最悪計算量には目をつぶりつつ実装する．それを提出すると…AC．なんと 2 位になっていた．しかし 1 位ははるか彼方の先にいる．それが東大のチームという現実を突きつけられ，絶望しながらも，わずかな全完逆転の可能性に賭けて私が J，nok0 が C を考察する．zkou は 2 人の考察の間を行き来していた．

私はやっぱり最後の最後で計算量が落ちずに完全に行き詰まっていた．nok0 が FPS の inverse を欲しがったので気分転換がてら実装したりしていた．

nok0 が懸命に C を実装するも，サンプルが合わない．J も全く埒が明かず，残り 10 分ほどで nok0 のコーディングを見守るだけになった．最後までサンプルが合わず終了．後で聞いたら微妙に考察に漏れがあったようだ．

結果発表

Yes/No の時間．結局我々は凍結後に提出していないので，3 位からどれだけ耐えてくれるかの勝負になった．kotamanegi_marunage とラズキャンに抜かれて 5 位で終了．ひとまず目標を達成し，去年の借りは返せたが，ラズキャンには結局敵わなかった．

表彰台で企業賞を渡され，写真を撮られた．そこから自分の席に戻る際には，安堵，感慨，疲労感，達成感，そして幸福感が入り混じった複雑な感情を覚えた．

終了後

料理がいっぱいあってすごかった． 交流が下手なので顔見知りばかりと喋った気がする．企業賞を頂いた MCD 様のブースに行くなどした．

会場を出た後は tokusakurai さん，torisasami さん，tabr さんと SPJ の 3 人の計 6 人でカフェに入ってだべっていた．適当な時間に切り上げて帰った．

Speed Star が優勝したことにより，チーム SPJ の今年の ICPC はこれで終了である．私は早生まれではないのでこのメンバーで出られるのはあと 1 回になった．

そして今年は DELIAIR と The Raspberry Candies の方々にとって最後の年でもある．東大に限らなくとも，現在の日本の ICPC チームで，全員が AtCoder で 2400 以上のチームというのはさほど多くない．だからこそこの両チームは貴重なライバルであり，同じ大学の仲間でもあった．

両チームの方々は全員が競プロに対して熱心で，東京周辺でオンサイトがあればほぼ必ず来ていたし，UCup にもほとんど毎週参加している印象がある． 競プロのイベントがあるたびに話すような人たちで，今思うとそれが自分やチームにとっても非常に刺激になっていたのだろうと思う． また全員が同学年であることもあり，お互いがお互いをバチバチに煽り合ったりするのも見ていてめちゃくちゃ面白かった．うちのチームも仲が良いが，それとはまた違う仲の良さだなあと思っている．

この 2 チームの方々の引退は本当に寂しい限りだ．人見知りなのでもうこれからオンサイトで誰と話せばよいのか分からなくなりそうだ．心配しなくてもあと 1 年で我々も引退なのだけれど．

今年で終わりの方々は本当にお疲れ様でした．またどこかで会って，競プロの話でもしましょう．

というか SPJ の ICPC ももうあと 1 回だけなのだなあ．有望な B1 のチーム，などと言ってもらったりしていたのがついこの間のように思い出せるのに．来年も同じメンバーで出るので，同一の 3 人で 5 年連続出場という珍しい記録になるはずだ．

粒揃いだった東大の 1 年上の代が引退したことで，来年は WF 狙えるんじゃないかと言われることもあるが，チームの力がそこまであるわけでもないので，正直他の強い人たちの意向次第だと思う．さすがに国内予選突破くらいは許してほしいけどね．下からの突き上げもあるけど，黄 x3 くらいのチームにはまだ負けたくない．橙 x3 くらいのチームができたら良いライバルになって良いなと思う．赤の人は出ないで本でも書いておいてください．

最後に，今年も ICPC を開催していただきありがとうございました．来年も行けるところまでやるんでよろしくお願いします．

*1:詳細な戦略については引退後に明かそうかなと思う

*2:運営には事前に伝えてあった

*3:こいつ ICPC 舐めてやがる

*4:これのために運営の方に何度も nok0 の到着時間について尋ねられていた．申し訳ない

*5:他のチームに見えうるから，という理由だったと思う

JAG 夏合宿 2023 参加記

ICPC OB/OG の会 (JAG) 様主催の夏合宿に参加してきた．非常に刺激的で楽しかったので，参加記を書く．

8/16 (Day 1)

Day 1 - Before Contest

院試が終了して自堕落な夏休みを送っているせいで生活リズムが破壊されており，前日の睡眠に無事失敗した．集合時刻は昼だというのに十分に睡眠がとれないまま荷物を支度して会場に向かう．会場はオリンピックセンターで，聞くところによると中高生の学術系のオリンピックの合宿などに使われたりするそうだ．

荷物を全部担げた方が移動の際に楽だという理由で，昔使っていた登山用のザックに荷物を詰めて来たのだが，これを背負って歩いているうちに昔を思い出して少し長めの距離を歩きたくなってしまった．

ソフトクリームを食べながら代々木公園を突っ切り，汗だくで会場に着くとチームメイトの nok0 と zkou は既に会場にいた．合宿楽しみだねーとか明日問題出すから頑張ってねー (nok0) とか喋っているうちにぬるっと合宿が始まる．Day 1 のセットは過去の韓国の国内予選で，3h 11 問だと聞いてびっくりした．時間の割に問題多くない？

Day 1 - During Contest

問題を紛失した上に内容もよく覚えていないのであまり書くことがない．A 問題で追加のおもりを片側にだけにしかのせられないことはもとの問題文にちゃんと書いてほしかった． 割と簡単な 6 問を通して，あとは椅子を温めて終了．長方形の数え上げが解けそうで解けなかった． 順位表を改めて見てみると，SSRS くんがソロ参加なのに開始 8 分で 3 問通していておったまげた．

Day 1 - After Contest

解説会が半分終わったところで夕食．知らない人に話しかけるきっかっけも特に得られなかったので，元から知り合いの東大生たちで固まって食べてた気がする．院試が終わったとか，rniya さんがまた遅刻したとか，そんな話をしていたら再開の時間になっていた．

残りの問題の解説を聞いて，ふーん結構うちのチームは苦手なセットだなあ…となった．なんか 1 問くらいは解けそうなのがあった気がするけど思い出せない．

部屋の鍵を渡されて同じ部屋の人たちと合流する． てっきりチームで同じ部屋になるものだと思っていたら，同じ大学の人が同じ部屋にいないように割り振られていた．結果的に交流が促進されて良かったと思う．部屋はベッドと机が 4 人分あるだけの簡素なものだった．参加費は 2 泊分とは思えないほど格安だったのでこんなもんだよね．

部屋では簡単に自己紹介をして，WiFi が使えるかどうかチェックしたりした．一応繋がるけどここにいる人たちみんなで ABC に出たりしたらヤバいかもな…って思うくらいの速度だった．

風呂に行ったらめちゃくちゃ混んでいて，シャンプーが付いているシャワー台の数が足りてなさそうだった．風呂の温度は結構高めで気持ちが良かった．

火照った体で眠い目を擦りながら ABC に出る．WiFi は相変わらず心配になりそうなくらいの速度だがなんとかなりそう．競プロはオンラインゲームなのに貧弱回線に優しい．

C は G の簡易版らしく，どうせ G を解かないと意味がないので C を飛ばす．ABDE を書いた後で F で手こずる．行きと帰りで高々合計 1 回，という条件があるときは行きも帰りも前から順に処理するというのはよくある話だが，なにを状態として持てばよいのかがしばらく分からず苦戦した．実装が終わって提出すると WA．かあ～っなんだよそれ．こっちは疲れてるんだから早く寝かせてくれ．ABC は Unrated だし，眠すぎるので普段ならこの辺で投げ出すのだが (おい)，同室の 3 人が真剣に解いているのでそんな気持ちになれなかった．かなり気付きづらいミスをしていて修正に時間がかかった．1 ペナで済んだ．

G はどう見てもフローっぽい制約だが，計算量がなかなか落ちない．とりあえず自明なフローの解を書いてみる．フローなら多少計算量が死んでいても通ることはよくあることなのでとりあえず出してみるも，落ちる． あの手この手で計算量削減を考えるも，結局どの工夫も TLE したままコンテストが終わってしまった．解説に書いてあることが頭よすぎて，同室の sotanishy 君となるほどね～って言ってた．

眠すぎるのでもう寝ようかなと思っていたら tokusakurai さんに将棋しようと誘われ，談話室に行って将棋を指した．ちょっと良さそうな将棋だったが結局負かされた．もう全然将棋やってないので何も手が見えないね．

日付が変わるか変わらないかくらいで部屋に戻って消灯した．ベッドが暑くてなかなか寝付けなかった．

8/17 (Day 2)

Day 2 - Before Contest

眠い．眠すぎる．目を開けたら部屋の人たちはみんな起きていた．この日は部屋の人たちと朝食に向かう．こんな早い時間に朝ご飯食べるなんていつぶりだろう，などという話をした．

コンテスト開始が 10:00 で，9:00 から準備と書いてあるがこれはコンテスト参加者も行かないといけないのか…？とみんなで議論していた．少し遅刻して行って知ったが，9:00 に行くのが想定解だったらしい．

今日は JAG の方が作ったセットだと思っていたが参加者有志でつくったセットらしい．チームメイトの nok0 が学会発表でいないため，今日は zkou と 2 人で参加することにした．nok0 が作問しているらしいのでどの問題がそれなのかを考えつつやろうかなと思った．

Day 2 - During Contest

問題一覧

zkou が A を読んでいる間にテンプレートを書く．書き終わって，さあどれを読もうかと言っていたらもう SSRS くんが 2 問ほど通しているのでありがたく追従することにする．zkou が A 問題で怪しげな式を提示してきたので素直に実装すると通る．続いて C を通す．H が解かれているので zkou にやってもらったところ，すぐに解いてくれて，これも通る．次に解かれている K を 2 人で相談する．しばらく 2 人で話したら頭がかなり整理されて，実装に自信が出たので書いたので通った．

この時点で開始から 1 時間から少ししか経っていないのだが，ここからが苦しかった．nok0 が用意したであろう数え上げの問題はやりたくないし，2 人しかいないので D のように実装が重そうなものはやりたくなかった．

E はどうせ閃き一発なのだろうと思って考えてみる．考察が進んで，かなり解けそうなのだが解けない．bitset を持つ全方位木 DP をしたら通るか…？と思って実装したらバグりまくって萎える．なんとかサンプルが通るもジャッジが RE を返してきてキレそうになった．てかこの方針 DOMjudge の環境的に無理じゃね？って言って，この問題に見切りをつけた．

しょうがないので通されている B と J を見る．B は数え上げで zkou 選手が匙を投げていたので考える気が起きなかった．J はグラフ上の未訪問の頂点に動くゲームだから勝敗判定条件を見たことがあるはずなのだが思い出せない．答え→グラフ上の陣取りゲーム – 37zigenのHP

なんかマッチングは関係してたよなー，と思いながらマッチングを考えてみると大体の盤面で完全マッチングに近いマッチングが取れることに気付いた．手作業で 3 * 3 と 3 * 5 のコーナーを確認して，まあどうせ他にもあるんだろうな…と思いながら投げたら AC して zkou と爆笑した．このあとコンテスト終了間際に DELIAIR も爆笑していたので何が起こったのか聞きにいったら，うちと同じことが起こったらしくめちゃくちゃウケた．

Day 2 - After Contest

解説会．やばいセットだとは思っていたが，解説を聞いたらさらにヤバさが再認識された．意外と nok0 が 998 を作っていなくてびっくりした．あとで聞いたら頑張ってジャンルを散らしたらしい．でもまあ J は予想どおりだった．

2 人しかいないし一番の数え上げ人材である nok0 がいないのでこんなものかと思ったが，さすがに B はやらないといけないっぽい．あと D も解説が始まる寸前に解法が思いついて，これも頑張らないといけなかったなあと思うなどした．

この日は終わったのが夕方だったので ARC までやや時間に余裕があった．普段ならこれだけ疲れていれば即刻仮眠をとるところだが，合宿だしやっぱ遊ばないとな～と思って同部屋の人たちと大富豪をした．久しぶりにこのゲームやると楽しいね．序盤でパスすることが tourist 出しとか呼ばれててウケた．いい交流になった．

ARC 20 分前くらいにお開きにして，コンテストの準備に取り掛かる．さすがに回線が心配なので回線が混んでいそうな最初の数分だけテザリングすることにした．ARC は前半でめちゃくちゃ手こずって死を覚悟したが，C を通した時点で 100 位くらいに回復して一安心した．D の解法がすぐ見えて，実装しているうちに最悪ケースの計算量が O(N2 M) くらいになりそうで怖くなる．でもなんか計算量小さくなってる気がするし…と思いつつ投げると一発で通って，うっひょ～ となる．今見返すと普通に O(NM) にしかなってないんだけどね．

数え上げには苦手意識があるので苦しみながら E を考えた．なんとか残り 10 分くらいで O(N6) くらいの解法が思いついて，これ 2 乗の DP で高速化できるか…？まあどうせこの残り時間で書くの無理やろなあ…とか言ってたら終わった．5 完が割といて，D 通した直後に比べて順位がめっちゃ落ちててちょっと残念だったけど，結果的にはかなり成功してよかった．

この日もまた将棋を指した．miscalc くんがべらぼうに強いことを知ってびっくりした．tokusakurai さんといい，同じ学科の 1 つ上と下の競プロプレイヤーにこんなに将棋強い人がいることある？？ 2 人と指して，両方負けたけど刺激的で楽しかった．特に miscalc くんとの将棋は結構アツい戦いで昔を思い出せた．

8/18 (Day 3)

Day 3 - Before Contest

2 日間で 4 つもコンテストをやってさすがに疲れた．眠気が Day 2 と比べものにならないが，チェックアウトの時間がシビアだったのでそんなことを言っている余裕もなかった．お腹だけは空いていたので食堂でおかずを食べられるだけ食べつつ，torisasami さんと昨日の ARC の話をした．

今日は 3 人揃っているし，昨日まで不甲斐ない順位ばかりだったし，今日は JAG の人が用意した 5h セットだったから，なんとか満足できる順位にしたかった．

Day 3 - During Contest

私が A，つちのこが B を通す．zkou と相談の上，簡単に解けた J を書いていく．nok0 が I を数分で書けると主張し始めたので交代し，その間に適当に問題を読んでいく．G は…7 sec だし無理ゲーそう．H は文字列だしロリハの用意もあるから行けそうに見える．

I が通ったので J の残りを書いていく．書けて提出したらなぜか WA が出るので不思議がっていたら，致命的なコピペミスがあったことが発覚し，思わず叫んでしまった．AC．

H を見返してみるとやっぱりハッシュとトライ木で log 2 個くらいでできそうだが，実装コストがそこそこ重いので先に nok0 に E をやってもらう．数え上げなのですぐやってくれると思っていたが，珍しく nok0 が手こずっている．なんとか AC したようなので H に取り掛かる．この時点で H に提出しているチームもなかったので本当に解法が合っているのか不安になった．書き終わって実行すると一発でサンプルが合う．マジ？！と叫びながら提出すると FA！FA は合宿で 1 回くらいやりたかったのでとても嬉しかった．

zkou と nok0 が C を解いたらしいので nok0 に実装してもらう．AC が出ている K について zkou と相談する．

zkou「ダイコネあればできるね」
私「今日用意してないよ」
zkou「アルゴリズムなら覚えてるけど」
私「？？？」
えー…知らんけどそれ絶対アルゴリズムめんどいやん，やるのめんどいけどまあやるしかないか…と思いながら zkou に説明してもらう．理解はできたが，資料なしで実装するの重いなこれ…．

nok0 が C で炎上しかかっていたので zkou が救援に向かう間に，K の実装を考える．なにぶん初めて実装するアルゴリズムなのでどのような値を保持しなければ行けないのか判断するのに時間がかかった．

C が通ったので zkou に横で見てもらいながらダイコネを書き始める．なんとか書き上げてサンプルを実行してみるとなんと一発で合う．えそんなことある？？？でもこれ Yes/No 判定だからどっかでミスってても分からんよな…とか思いつつ提出してみるとなんと通ってしまう．さすがに意味不明すぎて興奮した．

1 時間強の時間があったので 3 人で D をやった．蓄積した疲労のせいか，もうなんか色々バグったけど，なんとかいい順位を取って終わりたいな，という気持ちだけで色々やって，残り 8 分のところで 6 回目の提出が通った．さすがにもうできることもなさそうなので，もう終いでいいかな，と言って 3 人でお菓子を取りに行った．

Day 3 - After Contest

解説を聞いて，F と G でふーんと言っていた．F はまだ可能性あったけど G はマジで無理だ．
順位表の凍結が解除された．

最高の結果が出せて，とても嬉しかった．正直 tonosama か SSRS くんのどちらかには負けていたと思っていた．最後の最後で本当に良い思い出になった．

このあと打ち上げか何かがあるかなと思ったけど，みんな疲れていたのですぐ帰った．

Day 3 の終了後だけなぜか優勝者インタビューがあったのでそこでちょっとだけ喋った．チーム名の由来とかどうでもいいことを喋ったけど，普通に運営の皆さんや参加者の皆さんへの感謝を言えばよかったね．代わりにここに書きますが，運営の皆さん，交流して下さった皆さんのおかげで 3 日間本当に楽しかったです．ありがとうございました！

ICPC2023 国内予選・Kite_kuma (チームSPJ) 視点

1 年のときは比較的簡単な問題が 3 人揃って解けなかったせいで敗退した．2 年のときは 1 ペナ と 順位 1 つの差に泣いた．3 年のときは 序盤のスピードと zkou の天才的な閃きのおかげでギリギリ通過した．

国内予選は 1 年を通して自分の感情の起伏が最も激しいときかもしれない．今年もそうなるだろうと覚悟していたので，朝起きてからはずっと憂鬱だった．

いつものひとたち

  • nok0

    • 最近さらに数え上げに特化している．セットに 998 がないだけで文句を言うようになった．
    • 筋肉実装を嫌がらないのがいいところ．無限場合分けとかを投げられている．
    • 私が良く分からない問題に対して変な知識を披露して他 2 人をぽかんとさせたまま AC したりする．

  • zkou

    • 今年もやっぱりコードを書かない．構築ばかりやっている．
    • コードを書かなさ過ぎて，本人も最近は競技プログラミングをやっているのか，競技天才構築パズルをしているのか分からなくなってきたらしい．
    • どんな構築でも絶対に嫌がらずに明快な解を構成してくるので頼りになる．構築に敗北しているのを見たことがないかも．
    • 構築以外でも，適度な厳密さをもった議論に耐えうるので相談相手としては結構頼りになる．論理と直感のバランスが非常に良い人間だと思う．

  • Kite_kuma

    • 筆者．
    • 幾何とか構文解析をやる係．DP の遷移や添え字を詰めるのも 3 人のなかでは得意．
    • 他 2 人の補集合を埋める役割だが，ICPC 本番ではなぜかいつも思うように活躍できず萎えている．

チーム所感

  • チーム戦で各人がそれぞれの得意分野を解く，ということをやりすぎた結果各人が各分野に特化しすぎな感がある．チーム戦としてはこれでいいのかなあと思う反面，共有されていない知識が色々あるのは若干不安だったりもする．

5 月はじめごろ

去年コーチを務めてくださった方々はもう卒業してしまって大学に籍がないので，新たにコーチを探す必要があることは分かっていた． 5 月はじめごろに行った研究室見学の際に応対して頂いた先生にお願いしたところ，コーチと監督員を引き受けて頂いた．ありがとうございます．

東大の大半のチームはのいみさん経由で違う場所に集まってやっていたそうだが，PC の電源が 19 時に落ちるなどトラブルもあったらしいので巻き込まれずに済んでよかった．

6 月

ICPC の登録が始まり，国内予選を意識し始める．

去年の横浜大会前に購入したチームの共用キーボードでのタイピングに慣れるため，普段使っている HHKB を封印してこのキーボードで生活するようにした．

今年から国内予選も strict ICPC rule になっていることを知り，それに向けていろいろ準備もした．ライブラリなどの大半は去年の横浜で準備したものの流用で良かったが，初動をさらに早めるため冗長なテンプレートを削ったり，コード実行のための bash スクリプトを改良したりしていた．

まだ並列コーディングなしのルールにチームが慣れていないのもあったので，積極的に Universal Cup に出てチーム練習もした．毎週のように 13 問くらいのセットが提供されるのは本当にありがたい．

過去の国内予選や模擬国内などのセットはほとんどやりつくしているので，AOJ から全員が初見の問題を 8 問適当に抽出して 3 時間走るのも何度かやった．

模擬国内 2023

国内予選にガチなので，ちゃんと大学に集まって環境なども揃えてド真面目にやった．

このツイートだけだと zkou の行動は普通に見えるのだが，zkou は缶コーヒーを PC やキーボードを設置して模擬国内に臨もうとしているときに買ってきたのである．いやさすがに機械使う作業するときに蓋なしのもの買ってくるのはまずいだろ，と言いつつ缶コーヒーは必ず機械から 2 m くらい離れたところに置くようにした．

ちなみに菓子パンを買ってきたのは僕が食べたかったからです．

模擬国内の結果は現役チーム内 4 位で，いい感じ．他のチームがどのくらい真面目にやってるかは知らないが，このくらい本番もスムーズに進めば楽々通過なのにな，と思った．

1 週間前

1 週間で 3 回くらい 3h セットを走った．どれも前半の動きはどれも順調だったが，時間がギリギリアウトのところで高難易度の問題が通ったりと，なんとなく嫌な予感のする結果も多かった．

当日

寝るのが遅くて眠かった (おい)．忘れ物がないことを確認して家を出て，学科控室に 3 人で集合した．nok0 はある程度リラックスしていて，zkou はいつも通り飄々としていた．まーた今日も緊張してるの俺だけだな…とか思いながら会場に向かう．モニターやキーボード，プリンタの準備を整え，リハーサルで適当に 1 問通しておいた．

暇になったのでおやつを食べながら開始を待つ．去年は格上のチームが多くて一発当てる必要があったが，今年は自然に実力を発揮すれば通過ラインは超えそうだったので，ミスなく手堅く進めることをチームで再確認した．

競技開始以降

プリンタに問題文の印刷クエリを投げ，zkou に回収してもらううちに nok0 がテンプレートを書き，私が PC の左半分に表示されている A を読む．さすがに自明だが，焦ってもいいことは無いので制約などを 2 回くらい確認した上で PC を代わってもらう．印刷が遅くて nok0 が暇そうなので A の実装や提出するファイルが間違ってないかを横で見てもらっていた．

今回はファイルのダウンロードや提出を複数人で確認することが多かった．正直過保護すぎるほどだと思うが，手堅く進めるという方針と一貫していて良かった． 国内予選での 1 WA がどのような意味をもつのか，この 3 人は痛いほど知っている．

ほどなくして A が通る．B を書いてもらう間に C を考える．皆目見当が付かない．D を読み進める．これは自分が得意そうな問題だ．実装が済んだ B で RE が起こっていて，zkou が救援に回る．すぐ解決したので，構築だからと C を zkou に丸投げする．

nok0 が B を通して帰ってくる．C と D を読ませて，やはり C が全く分からなさそうだったので私と 2 人で D をやることにした．答えが 7 以下なのは明らかで，愚直に調べても状態数が binom(100, 5) くらいしかない．さらに様々な枝刈りも効くので現実的な時間で通るだろう，ということで解決した．私が D を書き始める．この手の探索は ABC で書かされまくっているので私 1 人で大丈夫だろうと思いつつ，nok0 には横について手堅く実装を見守ってもらう．あくまで手堅く行く方針なので，C も完成していない状況では E に行くよりこの方が良さそうだ．D のコードを実行してみると結構遅くて不安になった．nok0 指摘の適当な枝刈りを入れるとサンプルの答えが全部 7 になってあれ？？？このあたりで zkou が C を思いついていて，nok0 が確認に回る．正当性をすぐ理解できたようなので，私は D のコードを印刷して，PC を nok0 に譲った．

印刷したコードを見ても D のバグが分からない．nok0 が C を書き上げて提出する寸前に，チェッカーを書くよう言う．手堅く行くなら当然書く一択だ．幸いバグが見つかることもなく，問題なく C が通る．このすぐあとに D のバグが判明した．D の実行には 1, 2 分待った気がするが，これも無事通った．このあたりは理想的な序盤展開で，非常に喜んでいた．

D から帰ってくると 2 人は E をやっていた．手堅くやる方針なのでここも 3 人がかりでやる．しばらくしてセグ木を使った N2 log N が分かったのでこれを nok0 に書いてもらう．セグ木の写経ミスがないか確認したり，細かい遷移を詰めたりしているうちに，もう自分は必要ないと思ったのであとは 2 人に任せて F 以降を読み進める．

F は…なんだこれは．幾何は自分の担当ではあるのだが…．幸い入力が小さい整数なので整数で幾何の計算ができて，実装自体は軽くなりそう．G は計算量が指数になりそうな気がして嫌な気持ちになる．H を読んでいる途中で zkou が帰還してきたのでなんとなく得意そうな F を読んでもらう．nok0 も PC の実行待ちになったので待ちながら F, G を読んでもらう．実行が終わったので，また慎重に 2 人で提出ファイルを確認して E を通した．

5 完の時点で相当なリードを得ていたたが，まだ競技時間の半分も過ぎていないのでさらに考察を進める．nok0 は F がお気に召さないようで，G に行っていた．私と zkou は F をやっていた．私は少なくとも元の図形の凸包は埋めないといけないことを指摘したが，その方法が良く分からない．しばらくするとサンプルを眺めていた zkou が一言

zkou 「サンプル 3 (Yes のケース) のこことここって繋がるよね」

!?!?!?!!?!?!?!

確かに繋がってる...全く気が付かなかった．しかし手堅く行きたいので，他に何も浮かばなかったらこれを書くけどもう少しちゃんと証明してほしいと伝えた．具体的には，凸包の 1 辺と元の図形との共通部分の端点が孤立点である場合に，凸多角形を生成できないことを示してほしいと伝えた．私も一緒に証明を考えた．

数分経った頃に zkou が証明を思いつき，私に伝えた．公式解説にある証明とほぼ同一のものだった．このときの驚きと感動は形容しがたいものがあった．この短時間で，どうしてこいつはこれが分かるんだ…？こいつには何が見えているんだ…？

あとはこの証明をもとに正確な実装を 2 人で確認する．zkou に横で見てもらいながら実装して，AC．

もうほぼ確定なんじゃないかと言ったら，まだ 1 時間以上あるので万一 7 完勝負になったらまずいと言われて，余計なことを言って申し訳ないと思った．競技中は最後まで最善を尽くしましょう．

その後の nok0 と zkou の G の手際は素晴らしかった．適切に確率変数や期待値の記号を定義し，地道な式変形で最適化するべき式を正確に書き下した．余裕があるので 2 人で別々に書き下して確認したりもした．はじめは 60 の 5 乗だか 6 乗だかあった DP の計算量も，するすると落ちていって，最終的には現実的な計算量と簡潔な遷移に落ち着いた．

この G が通った時点で 3 位になっていて，自分より下にいるチームのうち 8 チームが全完しない限り 10 位以内になることが確定していた．H がどこにも解かれていないのもあって，この時点ではさすがに勝ちを確信していた．H を読みつつも，頭は完全に上の空．瞬間的に 11 位に落ちた東大のチーム RecEight に同情しながら応援したりしていた．競技中は最後まで最善を尽くしましょう (2 回目)．

その後順位が変わることもなく，無事に終わりを迎えた．

最高！

こんなにうまくいったの初めてなんじゃないだろうか．zkou さん，神すぎ…nok0 も，賢すぎ…てかまた俺なんもやってなくね？

去年通過していた Raspberry と DELIAIR もちゃんとすぐ下にいて，さすがだなあと思った．去年の横浜で惨敗した借りは返せたかな？また今年の横浜で会いましょう．

RecEight もなんとか最後に E 通せてよかったね．終了後に交流しましたが，来年以降のチャンスも多く残っているチームのようなので注目のチームだと思います．来年やられないようこちらも精進します．

そして Speed Star と tonosama の壁はやはり厚かった．今回のような理想的な動きでも時間で遠く及ばないのかと思って絶望しそうになるけど，横浜までにはもっと肉薄できるようになりたい．特に WF のためには Speed Star には勝たないといけないんだよなあ．今回の H は上位 2 チームが通していないために半ば諦めてしまったけど，言われてみればフローを疑うのはとても自然だし，そもそもこういうのを FA する気概じゃないと東大内 1 位なんて到底無理なんだろう．

去年の横浜は本当に悔しい思いをした．今年は絶対に悔いを残したくはない．

Cartesian tree の性質

列 a_0, \dots, a_{N-1} についての最小値を根とする Cartesian tree についての性質

  • 0\le i\lt j\lt N について，頂点 i と j の一方がもう一方の先祖である \displaystyle \iff \min\lbrace{a_i, a_j\rbrace} = \min_{i\le k\le j} a_k
    • 特に， i と i+1 は必ず先祖と子孫の関係にある
    • クイックソートの期待計算量の解析にもこの性質が利用できる

A+B と B+A がともに回文になるための必要十分条件

未証明だけど多分正しい主張

2 つの文字列 X, Y をこの順で連結したものを X+Y で表す．文字列 A, B について， a = |A|, b=|B|, g = \gcd(|A|, |B|), a' = a/g, b'=b/g とおく． A+B, B+A がともに回文となるための必要十分条件は以下の通りである:

  • S を A の先頭 g 文字を抜き出して得られる文字列とする． S' を文字列 S の反転とする．このとき A は S と S' をこの順で繰り返して得られる文字列で， B は S' と S をこの順で繰り返して得られる文字列である． 例えば A = S+S'+S+S'+\cdots+S+S' または A = S+S'+S+S'+\cdots+S'+S である．
  • a', b' のうち一方が偶数の場合， S は回文である．