ICPC 2019 Asia Yokohama Regional 参加記

11/18に開かれたICPC 2019 Asia Yokohama Regionalに電気通信大学からチームsushiで参加しました。

チームメンバーはfiriexp、kubo_nits、kenta2997(いずれもAtCoderのID)です。結果は4完25位でした。初参加にしてはまあまあ？

～コンテスト前日

国内予選が終わった後、USキーボードを購入して、メインで使った(送料込みで147ドル(練習とはいえ安いキーボードは使いたくないため))

チームでは何もしなかった(みんな忙しかったししょうがないね)が、個人では問題を解きまくった。結果AtCoderもCodeforcesも暖色になることができた。

前日に大学でライブラリと方眼紙を50枚ほど印刷した。

1日目(practice)

深夜コンなどで崩壊した起床時間をもとに戻すために、22時には寝て5時に起きた。TCO19 semifinalを観戦したりした後に会場に向かった。

駅から会場は少し距離があって、一人で来たら絶対迷ってるなと思った。会場で看板の写真を撮ろうと思ったが失敗した。

開会式とかいろいろな説明を聞いた後にpracticeセッションで環境の確認をした。

Aは問題を覚えてない。Bは少し誤読したが(解いたことあるのに)AC。

Cも解いたことがあったのでペアの全探索を解説してチームメンバーに任せる。AC。

Dは解いたことがなかった上解法が普通にわからなかったのでWAを出したり印刷したりclarを出したりお菓子を食べたりしていた。

その後はチーム紹介。みんな適度にふざけていてよかった。

終わったらそのまま解散、帰宅した。ABCもCFdiv2もunratedだし眠かったので寝た。

2日目(コンテスト)

5時に起きる。TCO19 finalを見ながらABCを解いた。Eが苦手なやつだった。Fは解法はすぐ浮かんだが家を出る時間になってしまったので解けず。TCOはhardが全部chalされていて面白かった。

朝早いし座れないのが嫌だったので、1回位はと思ってグリーン車に乗って行った。かなり快適で人権を感じた。

kuboさんが遅れそうだったがなんとか間に合う。コンテストがなぜか5分前に始まってびっくりした。

Aを解く。解けない。とりあえずAだし全探索だろｗとか思ったが全然そんなことはなかった。山は1個で十分だと気付くのにも時間がかかる。再帰で書こうとしたがBFSとDFSを間違えて時間をロス。(何色コーダーですか？)最終的には山の高さを全探索してAC(0:56)。大戦犯だ〜やらかしたとか思った。

その間に他の2人がBの考察を終えていたので投げて、AC(1:17)。その間に順位表を見る。Hがけっこう解かれている。

Hは括弧列の問題。典型通りに問題を変形すると、セグ木＋にぶたんを思いついたので書く。log2個の実装だったがとりあえず書く。WA。見る区間を間違えていたので書き直す。AC(1:57)。順位表をみるとEかGが次の狙い目。

Gを見る。01だし文字列長が16なのでbitDPっぽい。実際に文字列を構築していくことを考えると、prefixが一致していればマッチングでき、あまりだけを見れば状態数は $2^{17}-1$ 個なのでOKそう。でもダイクストラをすると計算量が不安なので、radix heapを写経して書く。煩雑なビット演算に悩ませられながら頑張って実装する。AC。(3:25)