ICPC Bangkok Regional 参加記 • knshnbのブログ

はじめに

ICPCという競技プログラミングの大学対抗チーム戦のアジア予選に参加しました。

チームは、去年の国内予選から組んでいるGirigiriです。

Joe: 序盤早解き・幾何とか実装・データ構造
おぎの: 数学・アドホック考察
自分: 典型dpとか・構文解析

役割は何となくこんな感じで分かれていて、特にJoeとおぎのが尖った得意分野を持っているため練習などでは個人個人の実力よりも高いパフォーマンスを出せることも多くありました。

参加まで

国内予選は24位ですでに敗れてしまっていたのですが、自分たちはM1でICPC最後の機会ということで海外Regionalに参加することにしました。行き先の候補はこんな感じで適当に決めました。蓋を開けてみると日本からの参加チームが異常に多く、同じ東大から日本で一番強いであろうUT a.k.a Isも参加していてびっくり。。。(legendary grandmaster3人のCafe Mountainとかいうやばいチームもいて、結果的にはかなりレベルの高い大会だったようです)

あとは、コーチが必要だとのことで、研究室の先輩(非競プロer)に頼んで快くOKしてもらいました。ありがとうございました。
なお、、、

研究室の後輩に「ICPCのバンコク大会に出たいが、コーチが必要」と言われてコーチになりバンコクまで付いてきたのですが、実はコーチは選手でもOK + 外部コーチは大会に来なくてもOK ということがここに来て明らかになり、ただタイ旅行しにきた人になってる。
— まむ (@mamurai1208) November 2, 2019

コンテスト

たぶんコンテスト出ていない人はつまらないと思うので飛ばしてください。

全体としての流れはjoeのブログにまとまっているので、自分の動きメモです。
ちなみに、順位表が見えたり見えなかったりrandomizeされていたりいなかったりする謎のコンテストでした。
順位表です。(現時点ではまだ問題のrandomizedが直ってない。どうにかしてくれー)

Bを読む。2次元グリッドの構築。パッとは分からなそう。
Cを読む。木。少し考えるが分からない。
Fを読む。誤差がよくわからないけどlog取ってワーシャルフロイドやるだけっぽい。Joeに説明して書いてもらう。WA。
Fいろいろ試すけど通らない。一応long double使ってるけどまだ誤差がやばいのかなあと思って素数制約とかをうまく使えないか考える。
Fわからない。このへんで1時間ぐらいたっているがJoeとおぎのがやっているDも原因不明のWAのままで、まだ1問も通っておらず絶望感が漂っていた。
F諦めて他の問題を読もうとしていたら、リジャッジされて通ったらしい。どういうことや。
JoeにKを詰めておいてほしいと言われるのでJoeがLCAを写経している間に詰めておく。本質部分は3行ぐらいになる。AC。ここの連携はかなりよかった気がする。
Joeとおぎのが最初からやっていたDが永遠に通らないらしいので問題を読む。おぎのに色々確認して素数列挙の個数が足りないことを指摘。直してもらってAC。
このへんでもうすでに2時間半ぐらい経過。順位表で通されているA,B,Iらへんを手分けして考える。Iは遅延セグ木に乗りそう？
AをJoeが書くがメモリが足りないらしい？解かれている人数的にA優先なので考える。
クエリソートしてBIT使えばできそうなので実装。TLEかなりギリギリそう($M=10^7$で$\mathcal{\Theta}(MlogM)$, 2秒)で、手元で測ると2.1秒かかったがジャッジ環境を信じて出す。TLE。
vectorを配列にしたりJoeに定数倍高速化をしてもらったりして出すがTLE。
おぎのに助けを求めると、$N$が$10^5$ではなく$10^4$だった(は？)。$\mathcal{\Theta}(N^2)$の方が早いのでそれで出す。AC。ここ時間無駄にしたなあ、、、
Iを考えると、{2乗和,1乗和,個数}を遅延セグ木に乗せれば解けそう。
おぎのがBが解けたらしいので聞く。合ってそうだけど掃き出し法でランク求めたりちょっと重そうで、グレイコード書ける自信もないのでIを優先することにする。
JoeがHのミスに気づいていったんPCから戻ってくる。
とりあえずPC空いている間に遅延セグ木を写経。
Joeがグレイコードの式を思い出したり、おぎのが考察を詰めて軽くなったりする。天才。
Iの計算部分を詰めている間にBを書いてもらう。
終了8分前に通る。すごい。
Iの続きを書くがさすがに間に合わず終了。

IとHという2問が実装キューに詰まったまま終了してしまうのは、5時間のコンテストでは初めてでした。結果的には、チームとして出せるパフォーマンスとしてはやや低めものもになってしまった気がします。

コンテストのワクワク要素の影響がなかったわけではないですが強いチームはこういった環境でも結果を残しているため、単純に実力不足を感じました。いつもは1-2人で通している問題にミスなどで3人がかりになってしまう事が多く、考察や実装を詰める部分が後手後手になってしまったのが反省点だと思います。

その他

1日目のpracticeで日本勢で優勝しました。笑
1日目の夜の観光後にHTTFというマラソンのコンテストに1時間参加したけどダメだった。eiyatonariのりっきーしーたぷにきあくんが同じ時間しか出てないはずなのに予選通過しててすごい。
順位発表のyes/noのスピードがめちゃくちゃ速かった。
コンテスト後の夜にAGCに出たら赤パフォを出してしまった。
タイのトムヤムクンはうまい(ここが本当におすすめです)。
Grabという東南アジア版のUberがあって、ぼったくられる心配などもなくかなり便利。市内の移動は数百円程度で、4人だと地下鉄より安いことも多かった。
日本語を勉強している学生ボランティアがbuddyとしてついてくれて、コンテスト期間中の通学のサポートや観光案内などをしてくれて助かった。
筋トレ+アユタヤ観光+タイマッサージという最強の組み合わせを見つけてしまった。

最後に

チームメイトの2人にはとても感謝しています。

自分は競プロを始めたのが比較的遅い方で、特に東大などの環境では楽しむのがなかなか難しいと思うのですが、同じレベルの仲間2人と切磋琢磨しながらここまで成長することができました。考察や実装などでお互い助け合うチーム戦は本当に楽しく、自分の中ではICPCが競プロの最も大きなモチベーションになっていました。