NOSSの雑記

主に競プロでやったことを書きます。

ICPC 2019 Asia Yokohama Regional 参加記

ICPC 参加記

チームEldoradoとしてICPC 2019 Asia Yokohama Regionalに参加しました。

チームメンバーの参加記

一日目

開場とともに入場。
あらゆる案内や受付が英語で「本当に英語しか使えない」ことを悟って内心動揺していました。大会中はほとんど「オーケー」と「サンキュー」くらいしか発言していませんでしたが...

チーム紹介文やコンテストのマニュアルを読んでいるうちに開会式が始まってリハーサルになりました。

リハーサル

nicklawさんが環境構築、Aをmhrb君、Bを私が読みます。

Aは自明らしいのでWAやREを出したりしてmhrb君がジャッジの確認をしていました。

Bは問題文が不明瞭で僕の英語力が足りず読解した内容とサンプルが合わねえ、となっていました。
チームメンバーに相談すると単語の定義をclarで質問することになり、その間暇なので多分この解釈だろうと信じて実装していました。 無事解釈が合っていたので提出するとWRONG ANSWER。明らかにやばい部分があるので直すとCORRECT。

Cを読むと明らかに解いたことがある問題なのですが肝心の解法が思い出せず。つらい。

このままリハーサルは終了しました。

Dの概要を聞くと脳内ACしたので、よし後はライブラリを写すだけだね、と該当のコードを確認すると...なんとJavaで書かれていることが発覚(メンバーは全員C++使い)。OBの先輩からいただいたライブラリはC++とJavaが混在していた...

チーム紹介

辞書順で後ろから順に行うことになり「Yokohama National University」の私たちがトップバッターに。なんの準備もしていなかったので簡単な自己紹介をして終了。他のチームは結構凝ったものがあったり、ネタに満載だったりとても面白かったです。

本番前夜

ライブラリが使えなくなったのでABC参加を断念しライブラリPDFを生成する作業をする。TeXの気持ちが分からず苦戦しました。

2日目

緊張で目覚ましより早く起きてしまう。集合時間より早く着いたもののやることもないので会場付近を散歩する。 ここで幾何ライブラリを忘れてきたことに気づく。まあ解けないしいいか...

無事に参加登録を終えて初動の確認をしていると、9:24頃に突然「1分後にコンテストを開始します！5分前倒しです！」とアナウンスが入る。
会場も少しざわく。さっきトイレに行った人が居たけど大丈夫か？と思いつつもコンテストが開始した。

コンテスト

リハーサル通りnicklawさんが環境構築、Aをmhrb君、Bを私が担当。

Bの問題文の単語難しいと思っていたらmhrb君がAを実装しながら詰めたいそうなのでお願いする。

Bは各マス目の高さを最小化する問題とわかったので、高さが決まったマスから高さ順にBFS的に決定して行けばよさそう。nicklawさんに解法を確認すると同意が得られたので実装方針を固めておく。

mhrb君がAを通す(0:22)。交代して私がBを実装する。提出すると難なく通る(0:41)。

ここから分担して解けそうな問題を探す。

C ぱっと思いつかない。
D 明らかにやばい見た目をしているので飛ばす。
E おそらく2乗DPだけど計算量が落ちない。
G 01のTrie木を書いたけどそこから進まず。

mhrb君がFをやってみたいそうなのでお願いする。

順位表を見るとHが解かれているのでHを考察する。Hはかっこ列を末尾に追加/削除する問題で、いつもの通り(で+1、)で-1するのを前から順にやるとかっこ列の数え上げができる。あとは削除に対応するためにstackで状態を復元できるようにすればいけそう。

mhrb君のFの考察が破綻してしまったらしいので交代してHを実装する。実装途中で考察漏れが発覚するもなんとかカバー。サンプルが合ったので提出するとAC！(1:48) この時点では18位ぐらいだったのでそこそこのペース。

実装していた間に考察してもらった他の問題の概要を聞く。

I 閉路は潰せるので木の問題になる。けど計算量が落とせない。
J やばい幾何。
K どこから取り組めばいいのかすらわからない。

順位表をみるとEが解かれ始めているので考察する。持つべき情報を持とうとするとどうしても3乗になってしまうので難しい。

あれこれ考えているとmhrb君が「二部グラフで解ける」というので概要を聞くと本当に解けているので感謝する。 あとはDPの漸化式を立てるだけでこの手のDPは解いたことがあるのでOK。私が実装に入る。

後ろで2人がおにぎりを食べていたので「早く実装をACしておにぎり食べたいなあ」と思いながら実装していた。このときかなり疲れていて実装がボロボロだったがmhrb君がペアプロでミスを指摘してくれたので助かった。 サンプルを試すと一発で全部合うので嬉しくなる。提出すると...AC!(3:22)

昼食を食べながら次に解けそうな問題を考えるとGかIあたりだったのでGを考察する。

長さ高々16なのでやるとしたらbitDPだろうなあと思いつつも漸化式が立てられずそのままコンテスト終了。

結果はABEHの4完でした。

閉会式

ICPC運営の方やスポンサーの方のお話を聞ききました。解説は全体的に賢そうでA,B,Hくらいしか理解出来ず。

ICPC恒例のYes/Noはすごい盛り上がってYesのときはみんなで拍手をして称えるのがいい文化だなと思いました。北京大学が最後Dを通していたのは激熱だった。

Eldoradoの順位は23位でした。

懇親会

全体での記念撮影と企業賞の発表があったあと懇親会がスタート。ご飯を食べたり、企業ブースをまわって展示をみたりゲームで勝ってカバンをいただいたりクイズを解いたりしていました。 5hコンテストをした後に企業ブースをまわるのが体力的に厳しかったのでもっと体力をつけたいなと思いました。

三日目

企業見学で私のグループはNEC->しながわ水族館->Huaweiの順に見学しました。

NEC
企業説明をしてくださった方々が競プロerの笑いを誘うのが上手くてさすがだなあと思いました。内容もとても参考になりました。用意していただいた昼食が非常に豪華でNEC本社ビルの眺望の良さも相まってとてもよかったです。

しながわ水族館
岩から湧き出る水をみて「フローだ！」と言っていたり、ペンギンの恋人関係図をみて浮気を切る最小カットっぽいと言ったり、イルカショークイズで盛り上がっている集団がいたり。なんだかんだ楽しめました。

Huawei
すべての技術を自分達で作り上げてやろうというすごい熱意とパワーを感じました。3DCGの話がとても興味深かったです。

感想

非常に楽しいICPCでした。去年に国内予選落ちをしてから臥薪嘗胆で精進をしていたので、今年のアジア地区で4完できたのはちゃんと成長できたんだなとちょっと安堵しています。とはいえ満足しているわけではないので来年は今回の成績を超えられるようにがんばります。