昨年11月に行われた2021年度ICPC国内予選から4か月が経った．あの日までチームとしても私個人としてもそれなりの量の準備をしていたため，敗北という事実は重く私の頭にのしかかった．あの日から2週間くらいは毎日敗北のことを思い返してはひどい喪失感に駆られていたし，今も月に1度以上はこのことで最悪の気分に陥る．私はこういうことをいつまでも引きずる人間である．
あの頃の自分達には何が足りなかったんだろう．ずっとそれを考えている．きっと運は足りなかった．運があれば行けるくらいの状況だったから．でももっと強ければそれでも行けたはずだった．今回はあの時以来のチーム戦だから，何か糸口が掴めるかもしれない．そんなことを考えながら模擬地区予選に参加した．
チーム名: SPJ
メンバー: クマー(Kite_kuma), zkou(zkou), つちのこ(nok0)
開始．つちのこが昨夜インドコンに出ていたことによって少し眠そうだった．問題が難易度順かどうか自信がないのでとりあえずつちのこがA，zkouがB，私がCを読み始める．Cがそんなに自明じゃなさそう．Bを見てzkouがASCII Expressionじゃんと叫んでいる．Aが通る．
Bを確認．ASCII Expressionの苦い記憶が蘇ってｳｯとなる．BCの難易度的に恐らく難易度順じゃないなーとなる．こういうときはいつも私が最後の問題から読み始めるようにしている．K問題を読んだ．同じような幾何の問題を以前に解いた気がしてきた．そうこうしているうちにBが続々と通される．特にThe atamaが8分で通していては？となる．冷静に見るとかなり単純な再帰降下で構文解析が行えるようだ．構文解析担当のzkouが書き始める．同じくらいのときにつちのこが易問のHを見つけて実装を始めた．
私はK問題に戻る．やはり既視感がある．この記事を書いているときに調べたが，感染時刻の復元以外は以前私が解いたEarth Observation with a Mobile Robot Teamの下位問題であるようだ．時刻の復元もアルゴリズムの中で自然に行えることなので，上に挙げた問題とほぼ同じ問題だが，それで実装をグダらせた苦い記憶が蘇って書くのを躊躇した．そもそもまだAしか通していないし，もっと自明な問題を見つけにいくべきだろうということで，discordにメモだけしてJを読み始めた．
J問題．なもりグラフの同型性判定．ループが1つだけあるから，各部分木についてハッシュを作ればよい．根付き木のハッシュは以前にこの問題で作ったことがある．各頂点 について，子の結果をマージして
の結果を得るのだが，その際に子のハッシュ値をソートするようにすれば，マージに非可換な演算を用いることができるようになり，適当なハッシュ関数でも壊れにくくなる気がする．未検証だが．この方法はソートにより計算量に
がついてしまうが，今回の入力の大きさなら問題ない．
ハッシュ関数を書いているうちにつちのこがH，zkouがBをそれぞれ通した．特にHはFAだった．運よく易問が早く見つかったのはあったが，チームで使用しているSCCのライブラリが縮約後のDAGを返す仕様になっていたことも地味に生きた．atcoder/scc はトポロジカルソートしかしてくれないので，少しだが時間の節約になっている．
国内予選の全方位木DPの問題についても思ったことだが，ライブラリの少しの工夫でミスの量や実装時間が抑えられたりするので，本番までにこういった部分についての整備も行っておきたい．もちろんそれを活かすためには，本番直前にはチーム全員で各ライブラリの仕様を確認する作業も必須だ．
Jのハッシュ関数が書き終わりそうになって，2つの数列をrotateして一致させられるかどうかの判定方法を考え始めた．ローリングハッシュがまず浮かんだが，正直1つの問題でハッシュを2回も使うのはなあ…みたいな気持ちになって少し嫌な気持ちになる．この抵抗感は以前に下のリンクの記事を読んだことも関係していた．
数列比較のRolling Hashは危険だよという話 - yukinote
そこで2人にいい方法がないか聞いてみると20秒ほどで「S+T+TでZ-algorithmやればいいよ！」と返ってきた．理解に10秒ほどの時間がかかったが，分かってしまえばあまりに手際の良い実装方針で感心した．サンプルも提出も一発で通って，FA．
そういえばコンテスト後に計算量 の根付き木の同型判定の決定的アルゴリズムを学んだ．まだ実装はしていないので，今後のライブラリ整備の課題としておく．ハッシュを使用しなければいけない今回のような問題もあるので，衝突確率の上界がある程度保証された根付き木のハッシュも作っておくことにしよう．
私がJを書いている間にIが書かれていて，JのACの2分後にこちらもAC．ここですぐできそうな問題が尽きて，順位表を見つつ各問題を見渡す段階に入った．確かこの時点では我々は2~5位くらいで，他チームが通している問題で我々が通していない問題はC，Gくらいだったと思う．
私が一番通されているGについて考えていたら，つちのこがCに興味を示し始めた．置換を制約とした最適化をしなければならないこと，制約が小さいことなどからフローであることは簡単に見当がついたので，どうせフローだよとだけ言っておいた．
私はGに戻る．10分ほど考えていたら隣接する2項をswapしたときのを影響が簡単に表せることに気付いて，そこからは早かった．最適化の典型的な手法なのでこれはもう少し早く思いつくべきだったとやや反省している．
つちのこがC，zkouがDをやっている間に，やれば絶対にできる問題であるK問題の存在を思い出し，私はそれの実装を始めた．SPJで幾何ライブラリの全貌をまともに把握している人間はたぶん私だけなので，幾何は私がやるしかない．先ほどこの問題はほぼ既出であると書いたが，人の軌道が直線なので過去問よりさらにやりやすくなっている．The atamaが38分でこれを通していたのには驚いたが，きっとokuraさんが経験を生かしてサッと書いたんだろうなと勝手に推測していた．
書いてみたら案外すぐ書けた．いつも思うが私は実装時間の見積もりが下手だ．誤差が若干怖かったものの，投げたらAC．チームメイトにはめっちゃ褒めてもらえた．やったぜ．正直そんなに大変じゃなかったけど．
1ペナを計上していたCも通り，これで8完となった．なんかよく知らないけどフローだったらしい．残るはDEF．
Dは面白そうな問題で，できそうな雰囲気があるもの，明確な方針は私にはよく分からなかった．Eが幾何だと聞いたのでとりあえずそっちを見ることにした．
Eを見る．多角形が凸なら円の存在領域は簡単な線形不等式で表せるので，計算が非常に楽になることに思い至る．…多角形が凸であるという制約がどこかにないか，目を皿のようにして探したが，特にそんな制約はなかった．
さて凸でないとなるとかなり大変である．当初は多角形を構成する各線分に対して円の中心の存在範囲がどのように制限されるかを書こうとしたが，やはり凸でないという制約が非常に邪魔だ．また が許容されるなら境界の点を全探索すれば円の中心が存在する区間が分かるが，今回の制約はそれを認めていない．その後も凸包を取ってみたりするなど思考は迷走を重ねた．色々考えた末にとりあえず円が内部に収まることと同値な条件が分かった気がしたので書き始めた．
私が幾何に悶絶している間，残りの2人はDの平方分割解を何とか高速化しようとしていた．いっぱいバグって大変そうだった．ペナも何回か出ていたが，結局2ペナACで助かったらしい．私はEはもういいと言ったので2人はFに行っていた．
ここでEの実装が複雑すぎて心が折れかかった．そもそも当初うまく書けたと思った条件が本当に正しいのか自信がなくなってきた．このままではまずいので，2人に現在の状況を共有しつつ実装を考え続けた．色々考えた結果，結局直線上を走査できることに気付いてなんとかACの目途が立った．30分ほどかけて書いて，AC．円を少しだけ小さくすると誤差落ちしづらくなることをzkouに教わったこと以外は全部自力だった．
私もFに加わった．区間Affine区間maxsumみたいな操作が必要っぽい．有志コンっていつもこういうわけ分からんクエリ問題が最後に残ってうちのチームが困ってる気がする．平方分割をまともに書けるようになるのも今後の課題だなあ，とか思いながらおやつを食べてたらコンテストが終わった．
結局AHBJIGKCDEの順で10完4位となった．
解いた問題のうちHJEの3問がFAで，これは全チームの中で最も多かった．難易度順でないセットでFAを取ることは運の要素も絡むし，的外れな順番で問題を解いた結果FAを得てしまうこともあるので，FA数の多さは戦略が優れていることの証左とはならないが，各問題で大きく出遅れることもなかったのでやはり結果としては上々だったと考えている．
コンテスト後に問題を振り返った感想．Cはフローを使うことはすぐ分かったが，愚直に辞書順最適を調べようとすると かかってしまい，そこからの進展が私1人では得られなかった．解説のように大きい定数を使うと複数要素の優先順位を定めることができるというのは1つの発見だった．まだまだネットワークフロー周りは練度が不足している部分が多いようだ．
Dでつちのことzkouがやった平方分割は頭いいし，解説の方針はもっと頭いいなって思った．こういう遅延処理みたいなの最近やってなくて全然思い浮かばなかった．
Fは今後の課題．こういうのを気合で通す経験がうちのチームの人間には足りてないのだろうと思う．二項間の差が定数以下だと分かっている場合に平方分割と相性が良い可能性があることが分かったのは1つの収穫ではある．
今回は練習試合だし，結果だけ見て国内4位だなどとそのまま素直に喜ぶわけにはいかないが，それでも確かな手ごたえを感じた．国内予選の時と比べても，我々は確かに強くなっている．FAを3つ取ったことで，順位表に頼らなくとも自分たちの実力で解くべき問題を見極められるのだという自信を得た．
あの頃の自分達には何が足りなかったんだろう．ずっとそれを考えている．きっとこれからも，競プロをやめるまではずっと．
