ICPC 2020 Asia Yokohama Regional Contest 参加記
NOSS, まほろば, まつしたの3人で横浜国立大学チームChabashiraとしてICPC2020アジア地区横浜大会に参加しました。
1日目
受付・開会式
zoomでカメラ越しに学生証を提示して本人確認をしました。
実は、ずっとオンラインのみで活動していたためチームメンバー全員の顔を見たのはこの受付のタイミングが初めてでした。
リハーサル
問題概要や考察をGoogle Documentに書きこんで共有する仕組みを導入してみたところかなり良かったので採用。
問題自体は去年のリハーサルの問題と同じだったのできっちりリベンジはしました。
Dで配列のサイズを間違えてREを出したのは本当に反省。
2日目
コンテスト
A,Bが比較的容易、C以降難易度ランダムのため Aをまつした君、Bをまほろば君に任せて、C以降をNOSSが読んでいく作戦。
C...ぱっと見やばそう。全くいい性質が見えないので飛ばす。
D...問題は非常にシンプル。ただ、点の数が多すぎるのでわからない。
E...明らかに幾何。読まずに飛ばす。
F...やや幾何。問題を読んでも特に何も方針が立たない。
ここでAのヘルプが来たので概要を聞くと、n * n * nの立方体から0の部分を削除して最後に投影図が成り立つか確認すればよさそうなのでそれを伝えて実装を任せる。
まほろば君がBを提出するとWAだったのでデバッグを手伝う。ここif elseじゃないとダメじゃないですか？等言っていたら色々自分で気づいたらしくいつの間にかACしていた。
Aの実装が破滅した報告が来たので、入力を逆順にすると配列の先頭と原点が一致するので楽そう、と伝える。まほろば君が詳細なデバッグにまわってくれた。
Jがかなり解かれているので読む。若干読解がむずいがナッツをとなりの頂点に押し出していくっぽい。木なので根からDFSすればよさそうなので実装する。やや実装に手間取ってしまい時間をとられるがAC。
この間に他の2人がG,H,Iの概要をまとめてくれた。
Hはgcdとlcmは素因数ごとのmin,max操作に置き換えられるから...？までいってそれ以上思考が進まず。
Gは連結成分がたくさんあって異なるグループ間でつなぎあう感じ。
頂点数vの連結成分は他方の連結成分をv-1減らせるのでl_iの値が小さいグループをa、他方をbとして(aの頂点数)-(aの連結成分の個数)+1>=(bの連結成分の個数)ならよさそう。
連結成分の個数はl_iが小さい順に見ていくとUF木でわかって、逆側もやれば両方のグループがわかる。
チームメイトに判定式があってそうか聞くと反例や正当性を確かめてくれたのでその間に実装だけ進める。
実装が終わるころには大丈夫そうという結論になったようでサンプルもあったので提出 -> WA...
l_iが同じ値の頂点がたくさんあったときにやばかったのでそこを直すとAC。
残り1:30:00で解けそうなのを探すとIがどう見てもDPなので頑張る。
考察するうちに数え上げPDFに載っていた問題を思い出したのでみんなで読む。
たぶん、こういう遷移だよなあ。とりあえず3乗で書くか。いやこの状態もつだけだとだめじゃね？と、みんなでうんうん唸る
最後にまほろば君に実装してもらったけどサンプルが合わずコンテスト終了。
解説・順位発表
去年と違い解説が日本語で聞けたので話は聞きやすかった。IがやっぱりDPなのが非常に悔しいのとCが左手法で解けてそれを5行で表現できると聞いたとき天才過ぎて感動した。
Yes/Noはやっぱり盛り上がった(Twitterが)
どのチームも凍結後にACを重ねられていて素晴らしかった。どこでこの差は生まれたのだろう...
僕たちのチームはABGJの4完で30位でした。
30位は企業賞としてLegalForce様からキーボートとノベルティTシャツがいただけるとのことで、初めての企業賞となりました。ありがとうございます！
その後は過半数のチームが6完していてすげーとなったり、eat_iceがどんどん上位に上っていくのが見れて楽しかった。そしてKINGのKINGっぷりがすごい。
懇親会
Gather TownというレトロRPG風のサービス上で懇親会をしました。
以前の会津合宿で同じチームだったsutaさんと話をしてちょっとエモくなった。チームUHISHIROは個人的に注目していたチームの1つだったので6完を見たときは本当に驚いた。おめでとうございます。
その後もチームUHISHIROの方々やふるやんさんなどいろいろな方と話をさせていただいて楽しかったです。
感想
結果は40チーム中30位と上位には食い込めず、オンライン、並列PDならではの作戦や個人の競プロ技術をもっと磨いておけばなあと後悔はあります。
でも、競プロをチームで取り組んだり、競プロをしている方々のとの交流ができ、企業賞ももらえて、オンラインでありつつも非常に楽しいICPCでした。
参加権はあと1回ですがまた地区予選に来れるように頑張ります。
