仮のブログ

仮です

JAG夏合宿2023 参加記

9/16,17,18の3日間でJAG夏合宿2023 2023/Practice/夏合宿/案内 - ICPC OB/OG の会 に参加しました. これはその参加記です.

day -inf~day 0

今年は数年ぶりに夏合宿が復活するというアナウンスがなされる. 存在は認知していて復活を待ち望んでいたので嬉しい. 横浜大会には通っていないが, 例年枠は余裕があるらしいので参加することに. このイベントが院試後のご褒美としてかなり院試勉強のモチベに貢献した.

day 1

コンテスト前

最初は夜行バスで向かうつもりだったが, 安くなかったので新幹線課金をして当日出発することにした. 最寄り駅に降り立つと競プロerらしき人がたくさんいた. 適当に近くで昼食(何かやたらとしょっぱく感じた蕎麦)をすませ, オリンピックセンターに向かった.

受付やら合宿のガイダンス等を済ませ, 早速1つ目のコンテスト直前となった.
ICPCのチームからはsota君と私が合宿に参加しており, もう一人チームに加えられるという事で, その場で同じくチームメンバーを探していたhourenさんと組み, 3日間の即席チームが完成した.
チーム名は, 双方の所属チームから一部をとってマージした, 「Aobayama_rHAPsody」 となった.
奇しくもメイドラの主題歌『青空のラプソディ』のもじりっぽくなっており, 気に入っている.

コンテスト

day1は韓国regionalの問題であった. 全11問で, 3時間. 同時コーディングや検索は禁止.
難易度がランダム順だったので, 3人でそれぞればらけたところから問題を眺めた.
A,Fをそれぞれsota君とhourenさんがすぐ解ける感じだったようだ. 私もKの方針が立ったのでサクッとACして早々にチーム3完をした.
その後はDとJが得意そうな見た目をしていたのでしばらく考えていたが, 進展無し.
それでもチームメイトが順調にC,E,Gの解法を生やしたらしかったので気楽に考察を続けられた.
コンテスト時間も残り少なくなってきたので, sota君も合流してJを考えた.
似たような問題の解法で平方分割を使うものがあった記憶があったので, 解法の見えぬまま平方分割というワードを出したところ, これが正解だったらしく, sota君が解法の形までもっていってACまで取ってくれた.
コンテスト時間も残りわずかだったため, お菓子を食べながら感想戦をして終了.
day1は7完6位.

コンテスト後

時間の都合上, 解説前半と後半の間に夕食が挟まった.
夕食は, 「青少年自然の家系統で出される夕食」として想像通りのものであった. 普段の学食がこれだとちょっとうーんとなるが, このような場所では寧ろ気分が出てこれで良いのだという気持ちになった.

解説会後はABCに出るか迷っていたが, 同部屋の人がボドゲをすると言っていたのでABCをさぼってそちらに参加することにした.
やったボドゲは ito, 犯人は踊る, なんじゃもんじゃ, テストプレイなんてしてないよ等. ほかにもやった気がするが思い出せなかった.
全員競プロ経験者という共通項があるので, itoやなんじゃもんじゃでそのようなワードを使うことが出来てとても楽しかった.

日が変わる直前くらいに解散して就寝.

話の流れ的に部屋や風呂について書けなかったのでここに書いておく.
部屋は4人相部屋で, 必ず他大学の人と組むようになっていたらしい. 部屋の内装としてはベッド, 机, 椅子が人数分あるだけの簡素なものであった. 競プロができるだけの机があったのが良かった.
風呂は宿泊棟2棟分の合同風呂で, 入浴のために棟を出て外を歩いていくのは少し面倒だった.
時間帯にも依るのかもしれないが, 大して混雑もしておらず, 快適に入れた. 印象的だったこととしては, シャワーの水圧がとても強く, ちゃんと持っていないとシャワーヘッドが吹っ飛んでいくほどであった.

day 2

コンテスト前

6:00 前くらいに自然に目が覚めた. 折角なので散歩にでも行くかと思って着替えたところで二度寝をしてしまい, 7:00に再起床.
その後は朝食を取ったり売店によったりして, コンテスト会場に向かった.

コンテスト

今日は有志セットで, 全12問5h. ルールは昨日同様.
開始直後にCを見ると, 円周角を見ると一発の問題であった. 実装も軽いのでコードを書き始め, FA. 特にday2全体のFAであった. 嬉しい.
次にAを見ると, これまた数学での典型問であったため, 手元で軽く確認した後実装し, AC.
次にHにとりかかる. 問題文の条件を整理すると, 二次方程式を解けばよいと分かる. 平方根操作が入るので, 誤差にやられないように丁寧目に実装してAC.
その後はKを書いていたsota君からhelpが飛んできたので, 全員でdebugをした. ほどなくしてヤバそうなところを見つけたので伝えたところ, 現在の方針ではすぐには修正できない感じらしい. しかし, すぐにhourenさんから別の解法が飛んできて, 無事ACした.
その前後に考えていたBも, 全てが計算できる形に収まった. 添え字合わせに若干失敗したものの, 丁寧に書いてACできた.
残りでは F,J が私担当かつ可能枠に見える. しばらく考えていたが, Fは考察が完全にとまり, Jも手元だけでやるには限界が来た. Dがいい感じになったらしいのでぼーっと話を聞きながらお菓子を食べていたら無事に通って, そこでほぼ時間終了.
day2は6完7位.

コンテスト後

夕食を食べたり入浴したりボドゲしたりARCで冷えたりARCの感想戦をしたりARCのWriter&Testerの話を聞いたりして0時ころ就寝.

day 3

コンテスト前

朝食を取ったり部屋を撤収したり売店に行ったり.

コンテスト

今日はJAGセットで, 全11問5h. ルールは昨日同様.
3日間で初めてA,Bに簡単枠があるとのことで, (Atcoderでない)じゃんけんをして, A: sota君, B: hourenさん担当で, C以降を私が見ていくことになった.
CDEFに998244353があったので, これを中心に眺めたり, サンプルを手で計算したりする. この4問で一番進展がありそうなのがCだったので, まずCにはりつくことにする.
2乗の計算量まではぱっと立式できるが, それ以上の高速化が難しい. そこで, 各項の直接計算は難しいが, 隣接項の差分計算は簡単なんだろうと思い, パスカルの三角形を書いたところ, 本当にその通りであることに気づく. 紙に解法をまとめ, デバッグ中だったPCを借りて実装, AC. その後, Iも直ったらしく無事通り, この時点でABCIJの5完となった.
Eを考えていたsota君から, 余事象を考えると見通しが良いと言われる. 確かにその通りで, 面倒な部分もかなり整った形にできそう. sota君から考察を引き継ぎ, 立式をしたのち実装. AC. この時点で, 順位表の上位はほぼ動きが停止していた. KにACが出ていたくらいで, 他の問題は提出すらなかったと思う.
どれを見ても激ムズだろうということで, 各自思い思いの問題を眺める.
私はFを眺めることにした. 4乗解はほぼ自明に生え, 差分更新を頑張れば3乗までは落ちる. しかし, この方針では2乗までは落ちそうに無い. このあたりで, 極大長方形や小さい領域のスコアの展開式を書くことなどを試したが, もう一閃きが足りず, 進展が無くなった.
Kは方針が立ったが通らないという事で, 全員でデバッグをすることにした.
解法も合っていそうだし, コードを見てもバグが分からない. しばらくして, 連結性の判定がおかしいことが判明した.
頂点倍化の方針をとっているので, サイズによる簡単な判定ができないことにチーム全員全く気付いていなかったのだ.
簡単な解決策が思いつかなかったので, 連結性判定用にもう一本ダイコネ作っちゃえをして無事AC.
順位表的に解けてももう1問くらいだろうということで, Hを考えることにした.
k=1の場合は, Trie木を作ればよい. しかし, そうでない場合が全く分からない.
しばらく唸っていたが, 各uは|s|の最大値で打ち切ってしまってよいことに気づく.
考えれば当たり前のことではあるが, |u|の総和のデカさに困っていたのでこの気づきが進展となった.
|s|の最大値でuが切れるなら, |s|が短ければ, trie木を辿っても, 現実的な時間で探索が終わる. |s|が長い時, そのようなsは少ないので何とかなりそう.
その後, そのような場合はロリハ+二分探索で行けると分かり, sota君に実装を任せる.
2.5secとはいえ, 平方分割+Trie木+ロリハ+二分探索で計算量がヤバい.
どうにかして定数倍高速化でもよいので改善方法を考えていたら, hourenさんから公式解説1にあったような方法が提示される.
議論を経て, どうやらその方針が正しそうである. 時を同じくしてsota君が実装を終えたので, ダメ元で一回出してみることに.
結果, AC. 歓喜感激.
解説会で聞いた話によると, TLを2.0secか2.5secか迷って2.5secにしたところそれに救われた提出が1チームあったらしいが, 我々のことだろうと思う.

残った時間はFの3乗解を投げてみたり, お菓子を食べたりしてまったりしていたらコンテスト終了.

day3は8完4位.
3日間を通じて, 6位→7位→4位と安定して好成績を取れてよかった.
3日間とも, 3人がそれぞれ強みを生かせたのが良かったと思う. 私自身も私が解くべき問題は概ね解けたのではないだろうか.

コンテスト後

解説会をして, そのまま解散.
夜行バスまで時間があったので, 東北勢数人と代々木公園で作問したりラーメン屋で作問したりマックで作問したりした.

さいごに

刺激的でとても楽しい3日間でした.
JAGスタッフの皆さん, 交流をしてくれた参加者の皆さん, ありがとうございました.