JAG 夏合宿 2024 に参加したので参加記を置いておきます。
きっかけ
去年もICPCのチームメンバー(miscalc君)と一緒に参加したので、今年も出ようということになり、参加した。チームメンバーの入れ替わりが生じて、今年はserendipity君を加えて3人での参加となった。
1日目
コンテストは韓国の地区予選のセット？で、3時間で12問だった。ABCD/EFGH/IJKLと分担して読み始めることに。
自分が最初に担当したI問題を読んでみると、いかにも「1問目」って感じの問題(ABC-Bくらい？)だったので早速実装してAC。最初に見た問題が偶然簡単だったので、I問題はFAを取ることができた。
解き終わったタイミングで、チームメンバーから「J問題が通されていて、チラっと見ただけだが見た目簡単そう」というような話を聞いたので読んでみると、確かにすんなりと解けそうな見た目だったので(ABC-Dくらい？)解いてAC。
次にK問題を見ると、かなりこの記事みたいな感じだったので、miscalc君に投げてL問題へ。この頃、miscalc君からもH問題のヘルプが来るが、悩んでいるうちに解決したので、KとHの2問の考察を任せてL問題へ。この辺りでseren君がE問題を通した。
ここからは、自分がL、miscalc君がA、seren君がCのような感じで、他の問題の進捗も見つつ頑張っていた気がする。L問題は幾何っぽいので自分の担当だと考えて頑張ったものの、解法に余計なlogがかかっていたためかTLEしてしまった(発想自体は近かったっぽい)。A問題は定数倍高速化を本気でやるくらいしか思いつかず望み薄で、C問題は構築が詰め切れず。最後30分くらいでBが解けそうだと気付き、seren君が頑張ったものの時間が間に合わずに終了。
5完13位。B問題に取り組めていたら良かったかもしれない。L問題みたいなのも通せるようになりたい。
1日目夜
ABC371に出た。ちょっと眠かったとはいえ、さすがにA問題に8分かけたのは意味不明すぎる。Fでバグを生やして結構時間を溶かしてGに取り組む時間がなかった。
2日目
コンテストは有志提供の問題セットで、5時間で14問。昨日と同様に、ABCDE/FGHI/JKLMNとほぼ3分割して取り組んだ。
昨日と同様、他の人が見ていない簡単枠をたまたま最初に見つけてFAを取れると嬉しいな～と考えていたが、JKLMNのいずれも難しそうだった。これらの中ではK問題が若干解きやすそうだったけど、それなりに考察は必要そうなので、いったん全問チームメンバーと共有することにした。その間にmiscalc君がAを通して、ほどなくしてseren君がGを通してくれた。
問題概要を共有すると、seren君がK問題を解いてくれそうな流れになった。また、Jもなんか行けそうな気がしたので、miscalc君と考えているうちに、かなり方針が立ってきたので担当。二分探索木を眺めて丁寧に頑張り、AC。なんとこの時点でJ問題を通しているチームはなく、2日連続でFAをゲット！
そうこうしているうちに、seren君がKを通してBに取り組み、miscalc君がFを通してNなどを考えていた。Bのヘルプが欲しそうだったので考察をすると、行ける気がしてきたので頑張って詰めてAC。そのうちに2人はMとNを考えてくれていた。miscalc君からNのヘルプが来ていて、こっちに集中。方針の誤っていた部分を約数包除で解決し、主に自分がNを取り組むようになった。同時進行で2人がMを考えてくれた。この分担ができたのはかなり良かったと思う。結果、MもNも終了10分前くらいにACが取れた。
8完7位。現時点の実力を出し切れたと思う。
2日目夜
みんな懇親会に行っちゃった……。「参加しても話せそうな人がいないんじゃないか」という消極的な理由で断ってしまった。もっと人と関わろう💪
特にやることもなかったのでAHCに出場。ヒューリスティック初心者過ぎて、かなり厄介な手法を頑張って実装した割に、素朴な貪欲よりも微妙な結果になってしまって悲しい。ビジュアライザを見るのが楽しかった。
3日目
コンテストは有志提供の問題セットで、5時間で11問。ABが簡単らしいので、Aをseren君が、Bを自分が担当し、miscalc君にはざっと問題を眺めてもらった。A,Bは早々にACを取った。
Bが終わったので、読まれてなさそうだった後ろから読んでいく。Kはグラフに対するいろいろなクエリを捌く感じで、Union-Findなどをちゃんと使えばできなくもなさそうという感じ。Jは変な問題だなぁと思いながら眺めていると、Dが通っていたので、miscalc君にKの説明をして一緒に考察。マージテクなど解法の本質的な部分が出てきて解けそうだと思ったので自分が担当し、ACをゲット。なんと、この時点でまだ誰もK問題を通していなかったので、3日連続でFAをゲット！！
ほどなくしてmiscalc君もIを通したので、3人でF,Gを考える状態に。Gはインタラクティブで、seren君が指数探索の方針で考察をしていて、その細部を詰めつつ、Fの考察を行う。どちらもそれなりに難航。Gはどうやら提案された方針だと回数がヤバそうなので、平方分割みたいなことをする変な解法を編み出した。ざっと計算すると、1100回まで許されている質問クエリを1100回くらい行う計算になり、さすがにギリギリすぎるだろと全員思いつつ、Gを自分が担当し、他の2人でFを考えることに。FはFで「辞書順何番目か」を計算するパートで頭がこんがらがったりしながらも、なんとかAC。残りの時間はGに取り組んだ。少しでも質問回数を減らす工夫をして実装し、チームメンバーにジャッジ側の挙動やランダムケースを書いてもらったりして、どうやら1100回は超えなさそうだということが分かり、提出してACを獲得することができた。
ここまでで4問を残して残り時間が30分くらいだった。ここまでも十分難しかったのだが、残り4問はさらに崖になっていて全然解かれていなかった。一応Cを考察して実験を書いたりしたが分かるわけもなく、ふざけて全問提出して凍結順位表のカモフラージュをしたら時間が来た。
7完8位。この日も自分のチームで出し切れる限界に近かったと思う。ちなみに、順位表のカモフラージュは、解けてないのに提出した4問のうち3問はCEだったのであまり成功していなかった。むしろ、順位表が凍結された瞬間に全問提出して結果8完していたtokusakurai氏(特別に1人で参加)の方が見事だった。
まとめ
3日連続でFAを取れたのは嬉しい。1日目は完全に偶然だが、2,3日目は解けそうな問題を解けると信じて取り組めたのが良かった。解けそうな問題を見抜く力はコンテストでも役に立つと思うので自信になった。
2,3日目はチームで出せる力をかなり出し切った感があった。ここから先は順当に強くなること、つまり解ける問題を増やしていくことが必要になると思うので、練習を重ねていきたい。
最後に、運営の皆様、夏合宿を開催してくださり本当にありがとうございました。