ICPCアジア地区横浜大会2019に出場しました

(2019-11-21, imported from team-seadrive.com/blog)

11/16-17 に横浜産貿ホールにて開催されましたICPCアジア地区横浜大会に Aobayama_dropout のメンバー(kotatsugame, Yukly, AokabiC)として参加しました。

1日目

なんかコンテスト感があまりない。準備も10分くらいで済ませて新幹線に乗車。例によってゆきのんが1分前に乗車する。

会場は去年と同じだったので、特に迷わず行けた。

開会式とpractice session

なぜAobayama_dropoutのチーム紹介文が空欄なのかというと、誰もsubmitしなかったからなんですねぇ〜〜〜〜(は?)

チーム紹介が白紙で、すいません。

practice用の4問は全部チーム練習で見たことがあるとこたつがめが言っていたが、そのときは大脳皮質が赤ちゃんだったので思い出せなかった。まあAもBも自明っぽいのでサクッと書く。

Cは言われてみれば二重階乗が組み合わせの総数になるみたいな話を大昔にした覚えがあった。Dはたぶんこたつがめが解いていた。

practiceで全完してお菓子エリアから他チームを眺めるのは気持ちがいいゾイ！

夜

ABCのため特に中華街とかにも行かずホテルへ。Fを通したかった。

2日目

コンテスト

突然開始が5分早まってめちゃくちゃテンパる。

今年はA, Bが難易度順らしい。Aを読む。だるそう……。

こたつがめが加速する回数で全探索を提案するので書く。終了条件を浅く見積もりすぎて1敗。さすがに注意力がなさすぎるので、低難易度帯もちゃんと埋めようね。

BはなんかBFSでがんばると通るらしいのでゆきのんが書く。通る。

Hが解かれているようなのでこたつがめがHの実装に移る。

その間にとっつけそうなEの考察に入る。んーDPっぽいが状態数が落とせない……。

Hを若干バグらせて苦しんでいたこたつがめが通して考察に合流。solveが少しずつ出てきたGの考察を並行で進める。

突然こたつがめがEの天才的な分割を思いついて聞く。天才過ぎて大声が出た。横で見守っていると通る。

Gは文字列長が16であることが鍵っぽい。余らせているsuffixと適当なprefixをつなげる形で最短路問題になって通る。

この時点で全体6位。やはりこたつがめは実装に強い。

あと通されていそうなのはCとI。~~というかスタートから半分たったのにACない問題が4問あるの異常じゃないか？~~

Iはチームで出ていた方針としては二重辺連結成分分解->橋の検出(Low-Link)->DFSで探索、というかなり重めの実装。他にどうしようもなさそうだったのでぼくとゆきのんは怪しい部分の考察を進め、その間にこたつがめが書く。

結局怪しかった部分も正しそう(実際にRobbins’ theoremと呼ばれる定理だった)で、残り45分くらいで書き上がる。バグとりを繰り返すがREが取れず終了。

5完16位。5完内では2位だったのでもう1完はしたかった(異常実装難易度セット感はあったけど)

懇親会

企業賞が降ってきてめちゃくちゃ喜ぶ。

ICPC Asia Yokohama Regional 16位でした。企業賞(LegalForce様)最高〜〜〜〜✌️✌️✌️

https://pbs.twimg.com/media/EJlQItvUcAYqwDi.jpg

ICPCは初めて見る人も多いので懇親を深めたかったが、Googleのギャグ問題に爆散される。まあ話したことない強い人と一緒に考察できたりしたからそれはそれでよかったか。

[* その後

ゲーセン組はあまりいなかった。みくにゃん&りあんさんとIIDXやjubeatをやったり、こたつがめが頓珍漢の宴AJ粘着しているのを眺めていた。

えっ、企業見学で水族館に行くんですか？ぼくは大学に行きます……。