ACM-ICPC 2017 アジア地区予選 つくば大会 (IQ1)
この記事はIQが1 Advent Calendar 2017の20日目の記事です
これ競プロのAdvent Calendarに投稿すればいいのに…
概要
タイトルに書いてある大会に、チームIQ1で出場しました。
目次
ICPCってなに？
ICPCはInternational Collegiate Programming Contest(国際大学対抗プログラミングコンテスト)の略です
ACMというつよい国際学会が主催しているプログラミングコンテストです
大学内で3人メンバー+1人コーチ(兼任可)でグループとなり参加します
グループが作れないと参加ができません
だいたい3回戦あると思ってもらえばよくて
- 国内予選(2017年は7月に開催、チームIQ1も通過)
- 各地区予選(日本チームはアジア予選) ←今回はこれ
- 世界決勝
という感じです
アジア地区は2回まで出場することも可能で、チームIQ1はつくば大会に加え 12/21~12/23のアジア地区ナコーンパトム大会(タイ)にも参加する予定です
世界決勝への選考方法は 世界大会への道 | ACM-ICPC 2017 Asia Tsukuba Regional に書いてあるんですが、結構難解です…
チーム構成
- メンバー(コードネーム/hatena id)
- 吹雪 / id:t-k3ntaroo
- 睦月 / id:smijake3
- 夕立 / id:chakku000
- コーチ
- shimomireさん
大会前日
某年会に飛び入り参加し、そこそこの量のお酒を飲んでいた
家に帰っても全然眠れなかった
1日目(12/16)
開始前
9時ぐらいに起きる→お酒が抜けてない+睡眠不足でとてもしんどい
JAXA見学のエクスカージョンを欠席にしていてよかった
13時過ぎにつくばに到着した
思ったより都会だった
適当に散歩したり音ゲーしたりしてから、14時過ぎに会場のつくばカピオに到着
ここでメンバーと合流した
受付に行くと日本人のスタッフさんが英語で話しかけてくる
どうせ日本語通じるだろうと思って日本語で返したりした
コンテスト会場に到着、自分たちの席に着く
日本人のスタッフさんが英語で写真撮らせてくださいと言ってくるので撮ってもらう
練習 (15:40 ~ 17:40)
めっちゃ暇していたらオープニングが始まる。
ホスト校(筑波学院大学)の先生方が英語でなんか喋ってる
海外の人も来てるから英語でやってることに気づく
練習セッションでは、3問のやるだけ問題で独自ジャッジ環境に慣れる練習をした。 それと並行して、用意されたUbuntuマシンのCapsLockをCtrlに替えてみたり、vimrcを書いて印刷したりしていた
歓迎会
ホスト校の食堂っぽいところまで移動して歓迎会が行われた
大学食堂が一通りのご飯を用意しているようだったが、うちの大学より明らかにクオリティが高く美味しかった、いい大学
そこそこご飯に満足したところでチーム紹介フェイズが開始
各チームが個性あふれる自己紹介をしたりしていなかったりしていた
私たちはIQが1だった
ホテル
1日目のコンテンツが終了したので自分たちで取ったホテルにチェックインした
疲労で動く気が湧かなかったので、しばらく布団で死体のふりをしてから大浴場に向かった
湯船の温度が死ぬほどぬるくてサウナでしか暖まれないのが悲しかった
2日目(12/17)
(用語集 AC:正答、WA:不正解、RE:エラー、TLE:実行時間超過)
7時に起きてホテルで朝飯を食べる
夕立ちゃんが布団で寝ようとするのを阻止してつくばカピオに向かう
コンテスト (09:30 ~ 14:30)
(この節長いし読みづらそう) 自分の記憶に基づいたお話です
会場には電子機器持ち込み禁止なので、カバンとスマホを預けて参考書だけ持って会場に入る。 昨日印刷したvimrcをカバンごと預けたことに気づいたのは開始直前で手遅れだった
09:30にコンテストが開始した
問題はA~Kまでの11問が英文で用意されていた。
まずは難易度の簡単と分かっている最初の3問をA:夕立 B:吹雪 C:睦月に割り当てる。
僕はPCの前にいたので、vimrcをちょっと書いたりCapsLockをCtrlに割り当てたりしてからBを読み始める
ちょっとしたら夕立ちゃんがAの実装を始める。 その間に僕がBの方針を思いつき、上手に全探索すればいいと分かる。
夕立ちゃんがA問題を提出してACだったので僕がBを書き始める(0:11)
後ろで睦月ちゃんがCの英文がむずいみたいなことを言っていて大変そうだった。
僕がBの実装を終えて提出したがWAになる。
PCを他のメンバーに譲るために、Bの解答を印刷してデバッグし始める。
コードを眺めていたらダメなところが分かったので、書き直してAC(0:54)
睦月ちゃんがCを完全理解していたので、実装を始める。
夕立ちゃんが D E F の問題文を読むということで僕が G H I の問題文を順番に読み始める。
読んでる最中に睦月ちゃんが C の解答を提出してAC(1:13)
夕立ちゃんが F の問題文が難しいと言っていたので協力して読んだりした
このあたりでは僕は F G H I の難易度を I < F < G < H かなあと(順位表を見ながら)判断して I を考え始めて、 夕立ちゃんが睦月ちゃんに問題情報を共有していた。 夕立ちゃんは E を、睦月ちゃんは F を中心に考え始める。
I の考察で1時間ぐらい試行錯誤した結果、「その区間と重複がある区間の個数」の最大値を求めればよいと分かる。 問題の制約上、各区間における個数は高速に求めないといけないので、睦月ちゃんに助けを求めて累積和をうまく使うやつを提案してもらった。 それで僕が実装して提出したらWAになった。 nandeyaとソースコードを見ていたら、入力を受け取る配列の長さが最大(2×10^5)の半分(1×10^5)しかない(´･_･`) 弱音をうだうだ言いながら訂正したらACになった(2:56)
再び順位表を見ると G が結構解かれていたので少し考えると、正四面体を展開して拡張した上で毛虫を直進させればよいと気づく。
夕立ちゃんとあーだこーだ言いながら考察を詰めて実装し、一発でACが取れた(3:28)
この後は睦月ちゃんと協力して F の考察をやり続ける。 いろいろ話した末に考察がいい感じに完成する
F の解法に必要なグラフ系アルゴリズムを書いたことなかったので睦月ちゃんにお願いする。 夕立ちゃんをPCから離して睦月ちゃんがPython3で実装を始める
Fを任せて暇になった僕は夕立ちゃんとEを考え始める。 いろいろ話すとその時点での解法に穴があったので、別の解法を考案する(後に分かるがこの解法も不正解)
睦月ちゃんがFの重めの実装を終えてちゃんと動いてそうだったので提出したらREとかTLEとかが出る。 そういえばPython2の処理系はpypyなのにPython3の処理系はCPythonだったことを思い出す。 なのでPython3コードをPython2コードに書き換えたがREが止まらない(険しい)。 この時点で残り30分ぐらいだった
REの闇が深そうなので睦月ちゃんがコードを印刷し、夕立ちゃんが E を書き始める。 その横で僕がコードのあら探しをするペアプロをしていた。 すぐに実装はできたので提出したけどTLEとかWAが出てウーム苦しい。 Fも怪しいところを少々修正しつつ提出したけどREが取れない
という感じでコンテスト終了Ω＼ζ°)ﾁｰﾝ
後味があんまりよろしく無かったが、そこまで順位は悪くなさそうだった
解説・表彰・閉会式
解説も英語で頑張っていた
Eの解説を聞いたら違った、FはなんでREなのか結局分からない
順位表の凍結が解除され、チームIQ1は14位だと判明した
so so だと思った
懇親会
壁際にステージ、中心にビュッフェ、周囲にスポンサー企業のブースという謎の形の懇親会が始まった
ご飯を食べながら企業のグッズをもらいに行く作業をしていたら、いきなりステージから呼ばれたので向かうとIBM賞をもらえた
その後適当にわいわいといろんな人と楽しく会話したりした
帰宅
宿は無いのでつくばからチームkurukuru-sushiと直帰した
めっちゃ疲れた
戦利品
写真撮るの面倒だったのでリストだけ書くと、
- オレンジ(contestant)のICPC Tシャツ
- ICPCと書かれたトートバッグのようなもの
- 各スポンサー企業の資料・チラシ
- 各スポンサー企業のグッズ
- チームでもらった企業賞(IBM)
- Watsonトートバッグ
- ノート+ハードカバー
- PCケース
- リングホルダー
- タンブラー
とかもらいました、御社すごい
まとめ
コンテストについて
全体を見るとだいたい普段の練習ぐらいの調子だったかなと思ってます。
追記
チームIQ1はアジア地区ナコーンパトム大会に参加する予定で、現時点(2017/12/20 22:00 UTC+7)でタイにいます。
がんばるぞい🇹🇭
