JAG 夏合宿 2023 参加記 - sotanishy.shojin();

9/16〜9/18 に国立オリンピック記念青少年総合センターで開催された JAG 夏合宿 2023 に参加した．

Day 0

高速バスで仙台から東京に移動．合宿参加費 <<<<<<< 交通費 (安くしてくださってありがとうございます)

Day 1

12時半ごろにオリンピックセンターに到着．建物がめちゃくちゃでかくてびっくりした．

参加者は思ったより多くて60人くらいいた．色々な大学から人が来ていた．自己紹介のあとチームを組んだ．ICPC チームの suzukaze_Aobayama からは僕と仮の人くんが来ており，一人足りない． houren さんがチームに加わってくれて，チーム Aobayama_rHAPsody が結成された．

この日は 14:00-17:00 の3hコンテスト．全11問．韓国の国内予選2022で使われたセットらしい．

https://www.acmicpc.net/category/detail/3217

当日の順位表が見つからなかったのでどういう順番で解いたのか覚えていないが，僕は CEGJ を解いた．CEは簡単，Gはチームメイトが考察していたのでそれを聞いて実装，Jは難しかったが頑張った．Jは面白かった．平方分割の方針で考えても何を平方分割すればうまくいくのか見えづらいし，うまく平方分割したあともそのあとどう処理すればいいのか結構考える必要がある．解けてかなり達成感があった．

結果はたしか7完？で順位は覚えていないが1桁の悪くない順位だった気がする．

解説を聞いた．HIが不可能でやばかった．韓国の国内予選ってこんな感じなんだ．この問題数を3hでやるのは大変そう．

その後部屋に行った．ルームメイトと話したり風呂に入ったりABCに出たりした後12時に寝た．次の日の朝は早い．

Day 2

7時起床．10時から5hコンテスト．この日は有志セットで，全12問．この日も Aobayama_rHAPsody で参加．

yukicoder.me

僕は後ろから見て行って，Kでそれっぽい解法が生えたので実装した．ただ投げても投げても通らない．チームメイトに救助を要請すると， (a, b) が unique でないときに壊れていることが指摘される．勝手に (a, b) が unique と仮定してしまい，それでしか動かない解法を考えてしまったので振り出しに戻ってしまった．ところがすぐに houren さんがいい感じの解法を生やしてくれたので実装して AC．5ペナも吐いてしまって申し訳ない．

Kで悪戦苦闘している間にチームメイトがACHを通していた．また，Kを通したちょっとあとにBも通る．

Dが解けた気になったので実装に移る．かなり面倒なことをする必要があって， houren さんと話しながら丁寧丁寧に書いていった．オイラーツアーを取って区間加算区間 min を頑張るのが解法だが，遅延セグ木を使いたくなって絶望していた．ここで，平方分割でサボれないかと指摘され，それを採用することに．遅延セグ木を平方分割で代用するみたいなコピペなしコンテスト特有の発想がなかったので，これはかなり勉強になった．めっちゃしゃべりながら実装したおかげでいろいろ整理できてスムーズに実装できた．チーム戦のいいところ．サンプルがあったので提出すると，一発でAC．特大のガッツポーズが出た．

それ以外は解けずに6完7位で終了．この日も悪くない順位を取ることができた．KでやらかしたがDで取り返せたのも満足．

解説を聞いた．なんかいろんな意味ですごい問題だらけだった．コピペなしのコンテストで重み付き一般マッチング想定が出たのにはさすがに笑ってしまった．

飯を食べて風呂に入って部屋に戻る．ARCまで1時間半くらい時間があったので，ルームメイトと大富豪をやった．久しぶりに大富豪やったけど楽しすぎる．潜伏して tourist 出しする人がいてウケた．僕は基本的に貧民をやっており，資本主義の残酷さを思い知らされた．

9時からARCに出る．いつもratedコンテストのときは耳栓をしているが，今日は持ってくるのを忘れてしまったという話をしたら，ルームメイトが大量に耳栓を持ってきていたので1組譲ってもらった．この日の配点は 4-6-6-7-7-8 というなんともやばそうな配点でビビっていたが，結局Dまで解けて暖まったのでうれしい．Dがかなり面白いと思った．

ルームメイトと軽く感想戦をするなどしたのち12時に寝た．

Day 3

7時起床．9:45から5hコンテスト．JAG セット．11問． Aobayama_rHAPsody.

ABが簡単らしいので，Aをチームメイトに任せてBを見る．すぐ解ける．

その後，後ろから問題を眺めていった．IJにACが出ていたので，僕はJを見に行く．グリッドでうまく動いて，パス上の文字列を並べたものと目標の文字列の編集距離を最小化する問題．編集距離の気持ちになると，グリッド上の位置と，何文字一致させたかの状態を持ってDPすれば良い事がわかる．遷移がDAGじゃないので，01BFSをする必要があるということにちゃんと気づけて，AC．

その後チームメイトがCとIを通す．偉すぎる．

Eが解かれているのでEを見る．余事象を考えると，出現した数字の集合が常に区間になるようにすれば良いことはすぐ思いついたが，立式が下手すぎて計算できない形にしかならなかった．仮の人くんに見せたらいい感じに整理してくれて，実装してもらいAC．

Kを見ていたら解けた気になる．ある頂点に行って戻ってくるという操作の性質に気づいて，頂点数の偶奇とパスの偶奇を考えれば，動的なグラフで連結性判定と二部グラフ判定ができれば良いとわかる．Offline dynamic connectivity を写経してサンプルを合わせて投げるが通らない．チームメイトにも考えてもらい，解法の正当性を検討してもらったが，考えれば考えるほど正しい．全然わからないので諦めて昼飯を食べていたら，連結性判定がバグっていることに唐突に気づいた．UFで二部グラフ判定をするときに頂点倍加をするので，そこで連結成分のサイズをみるような連結性判定が壊れていた．直したら AC が帰ってきて大喜びする．

他に解かれているのがHしかないので見る．k=1の場合はトライ木で処理できることにチームメイトが気づき，あとは平方分割して大きいやつをロリハ，小さい方をトライ木で処理できることがわかった．制約とTLに対してこの解法の計算量が重すぎるので通る気がしなかったが，ダメ元で書いてみる．サンプルを合わせて投げたらなんか通ってしまって，チームが沸いた．

残り1時間位で，残りの問題を考えてみたが全然分からなかった．

8完4位で終了．最終日にとても良い結果が出て良かった．即席のチームだが，3日間を通してチーム全員が結構貢献できたのでとても楽しいチームだった．

解説．HのTLを2secにするか2.5secにするかで迷い結局2.5secにしたらしい．2secと2.5secの間に入ったチームが1つあったと聞いて我々のことかな？と言っていた．解けなかったDFGのうち，DGはかなり大変そうで，Fは思いつきたかったな〜という感じの面白い解法だった．

解説後に解散．東北勢と夜飯を食べて深夜の夜行バスで帰った．