JAG夏合宿2024参加記
ICPC OB/OGの会(JAG) が主催している、2024年の夏合宿に参加しました。
この夏合宿はICPCという大学対抗のチーム制プログラミングコンテストのアジア地区予選大会に向けた強化合宿で、３日間アジア地区予選形式の問題を合計13時間かけて取り組んだり、他校の競プロerとの交流を深めるイベントです。
来年以降の夏合宿に参加する人の参考になったり、コンテストの問題を解く参考になれば幸いです。
Day -1
ICPCの同じチームの先輩からJAGの夏合宿に誘われたので参加することにしたものの、その先輩は多忙により欠席してししまったことにより、僕の大学からは一人で参加することになりました。 ドキドキですね。
Day 0
この合宿にひとりで参加するので他校の人と僕のキーボードを使うかも知れないということで[1]気合を入れてキーボードを水洗いしたところ、スペースキーが効かなくなりました。びっくり。
Day 1
集合時刻の1hほど前に最寄り駅の参宮橋駅から出たところ、キャリーバッグを持って歩いているいかにも合宿参加者！という人を見かけましたが、社不なので話しかけずにスルーするなどしていたらなんだかんだガイダンスが始まりました。
参加者全員の自己紹介があり[2]、「気合入れてUSキーボード水洗いしたらスペースキー効かなくなりました」と言ったところややウケしたの嬉しかったです。笑ってくれたみんなありがとう。
JAGスタッフのみなさんが余った人間のチームマージを斡旋してくれたおかげもあり、早稲田大学のtcknyoというチームに混ぜてもらうことになりました。 ありがとうございます！
コンテスト day 1
結局チームメイトのtokuさんのキーボードを使うことになりました。 この日のコンテストは 2021年の韓国のICPC国内予選の過去問を使って、コンテスト時間は3時間、問題数は12問、問題順と難易度順はあまり関係ないらしい、というものでした。
オンラインジャッジが https://www.acmicpc.net/category/detail/2810 にあります。
チームメイトで分担して問題を読むことになり、僕はI→J→K→Lの順で読む担当になりました。
Iが比較関数を定義してソートするだけのやるだけ問題だったので真っ先にPCを使って実装したのですが、ビブスの番号でタイブレークするということに気がついておらず1ペナ出しながらもなんとか通しました。
Jを読んだところ、これもまた簡単そうでした。「二次元累積がないと厳しいよ～～～」などと意味不明な主張をするなどしている間[3]にチームメイトのキクタンさんが通してくれました。
どういう経緯だか忘れましたが、Hを読んでキクタンさんと考察をしているうちに、(p,q)をpの昇順にソートして平面走査をすればいいということに気が付きました。
結局、
と定義して
コンテスト中はpが同じときのstackみたいなものを管理してなんとかするというのをtokuさんに実装してもらってなんとか通せたのですが、今考えると「leftsを求める前にはp昇順q昇順にソートして、rightsを求める前にはp昇順q降順にソートする」という方針なら実装が楽になったんじゃないですかね?[4]
Eは主にtokuさんが実装していて、DPであることはずいぶん前から気がついていたものの、「平均値との差の二乗の総和を求める」という問題を「分散を求める」という問題だと全員が勘違いしていたためにめちゃめちゃ時間がかかってしまいました。
その後方針はわかっているBを書いたりしたものの通らず、27チーム中23位で終わりました。
コンテスト後
解説を聞いたり夕食を食べたりしました。宿泊する棟の横で温泉みたいな何かが湯気を立てていたのがアツかったです。
(湯気に近いほど植物が枯れているあたりちゃんと硫化物系のガスみたいなのが出てそうです。ふんわり匂いもしました。)
この日のABCのために、JAGスタッフの方が宿泊棟の談話室にWiFiルーターを置いてくれたらしくそこで参加しようと思いましたが、イカつめのおじさん[5]がカップラーメンを机に積みながらテレビをつけていたので談話室からの参加は諦めて部屋から参加することにしました。が、テザリングがうまくいかなかったためスマホで問題文を読んでPCで書いたコードをBluetoothでスマホに転送して提出することにしました。めちゃめちゃやりにくく、モチベが下がっていたこともありちゃんと不調という感じの結果に終わりました。
Day 2
コンテスト day 2
この日は有志セットを 14問5hで解くコンテストでした。
前日と同じように読む問題を分担しました。たしか僕はK,L,M,N担当だった気がします。
Kは難しく、Nはギリ考察すれば解ける枠ではありそう、みたいなことを言った気がします。
序盤にAをtokuさんが通していました。
F問題でクエリによる変更があることに気が付かず、tokuさんと一緒に議論した結果ほぼやるだけだという結論になってしまいました。前日にも誤読の前科があるのに二度目はまずいです。
クエリのあるFを考え続け、「HL分解と遅延セグ木があれば出来る」などと主張をしていましたが、HL分解のライブラリを持ってきているわけでもないし、tokuさんが「HL分解と遅延セグ木にしては解かれすぎているので他の解法があるはず」と言っていたので永遠に考えていたところ、結局クエリの影響は変更される頂点とその親の、たかだか２つの頂点にしか及ばないことに気が付きました。
途中何度もバグらせたりしたもののなんとかFを通しました。
Gをバグらせつつもキクタンさんが通したり、Nをtokuさんが通すなどしてコンテストが終わりました。
このセットのオンラインジャッジが生えることに期待してます！
コンテスト後
懇親会に行きいろいろな人と話したりしました。数学科以外の理系にはどうやら実験があるのは普通らしく、実験トークでみんな盛り上がるなどしていました。
懇親会の後にAHCに出ました。マンハッタン距離での最小全域木のライブラリをインターネットから窃盗して利用しようとしたものの、そもそもこの問題の出力形式に合うような順序で出力するのが難しく、無限にバグらせていました。
(マンハッタン距離の最小全域木に採用される辺のすべてが、問題の制約を満たしながら貼れるわけではないのでその辻褄を合わせる工夫がないとこのような無惨な後半になってしまう)
Day3
チェックアウトで鍵を渡した際に、僕の部屋番号の言い間違えをルームメイトが指摘できたものの、そのルームメイトも部屋番号を間違えてしまったシーンがハイライトでした。
コンテスト day 3
この日のコンテストは JAG運営陣のセットで、5h 11問のセットでした。
この日はA,Bが簡単と言及されていたこともあり、B,I,J,Kを読みました。[6]
キクタンさんがAを通した後、ウンウンうなりUnionFindを使いながらなんとか(0ペナで！)Bを通しました。
Iの概要をtokuさんと話しているうちに状態数を2個持つDPをtokuさんが思いつき、通してくれました。
この時点での順位表情報ではF,G以外に解かれている問題がほとんどなかったためF,Gを3人で並行して考えます。
Gは De Brujinグラフで考えると良いんじゃないかという方向性になっており( https://en.wikipedia.org/wiki/De_Bruijn_graph ) 、De Brujinグラフを僕は知らないためずっとFを考えていましたが、コンテスト中に解ききることはできませんでした。
このコンテストのオンラインジャッジが生えることをめちゃめちゃ願っています!
コンテスト後
最終日のコンテストも終わり、みなさんと連絡先を交換するなどして解散しました。
最後に
最高に楽しい３日間でした。JAGの運営スタッフや、有志セットの作問者さんなど全方位に感謝しています！
皆さんも大学生でICPCの参加権がある方は夏合宿に参加してみることをおすすめします！
ところで、こんな日記みたいなことZennに書いて良いんですかね？ 怒られたらなんとかします。
夏合宿関係者の方でこの記事の内容に不適切な部分があることに気がついた方は、TwitterでDMしていただけるとありがたいです。
Discussion