ICPCアジア地区つくば大会参加記

この記事はtraP Advent Calendar 12月20日の記事です。

こんにちは、batonです。

先週の土日(12/16,17)につくばで行われたICPCアジア地区つくば大会にnari, ninja, batonの3人でninjaribatonとして参加してきました。

結果は7問解いて5位(大学別3位)でした。

はじめに

ICPCとは、国際大学対抗プログラミングコンテスト(International Collegiate Programming Contest)のことで、大学生(高専生)のための競技プログラミングの大会です。
今回開かれたICPCアジア地区つくば大会は、今年7月に行われた国内予選の通過チームといくつかの海外チームが参加でき、来年4月に中国で開かれるWorldFinal(以下WF)への出場チームを決めます。
競技プログラミングについてはこのページ、予選については、このページを見てください。

ICPCの特徴

ICPCの特徴としては、

1チーム3人
使えるPCが1チーム1台のみ
問題文が英語

競技プログラミングのコンテストでチーム戦として行われるものはほとんど無く、多くの人が慣れていない分、時間の使い方や役割分担がかなり重要でそれによって大幅に結果が変わったりします。

チームについて

ninjaribatonは、traPメンバーの3人で構成していて、学年がB1, B2, B3とバラバラで、さらに全員がアジア地区初参加です。3人が解く問題があまり被らないので、チームとしては良い感じです。

東工大では、他に2チームIQ1とkurukuru-sushiがこの大会に参加しています。

ここからは時系列にそって書いていきます。

0日目(前日)

木曜から金曜にかけてチーム練習用のVirtualContestがあったので空きコマにやろうと思っていたが、ライブラリの整理と、環境設定のまとめを作っていたら空き時間を全て消費してしまった。
夜は、帰るのが遅くなってしまったので、ライブラリだけ印刷して、すぐに寝ました。

このときは、1桁順位がとれればいいな〜ぐらいの気持ちでした。

1日目

朝は、まぁまぁ早く起き、つくばに向かいました。

午前中はエクスカーションでJAXAつくば宇宙センターの見学に行きました。見学後に昼食が配られたのですが、センター内に座って食べる場所がほとんど無く、バス内で食べることになってしまったのは悲しかった。

その後は、エクスカーションも終わり、プラクティスのためにコンテスト会場へと向かいました。
コンテスト会場内の公用語は英語で、受付も案内もすべて英語という英語が苦手な自分にはかなり辛かった。辛いのは参加者だけで無く、スタッフもで、途中から荷物の預かりなどコンテストに直結するもの以外では日本語が使われるようになっていった。

プラクティスは、環境設定の確認とジャッジシステムの確認を行う時間で、やったことは、

Ubuntuの操作確認
標準エラー出力を行ったときのジャッジ結果の確認(デバッグで使用する)
スタックメモリ上で1GB確保してみる(なんと、上限が2GBだった)
assertを行ったときのジャッジ結果の確認
印刷の改行やタブの表示の確認(ちなみにタブ幅はスペース8個分でした)

など結構こまかくやりました。本番に環境で困ることがないように初めての場合は結構念入りにいろいろ試してみると良いと思う。

その後は歓迎会で、そこでは英語でのチーム紹介という難易度の高いことを要求されたが、全部nariさんがやってくれたので、何もせずに終わった。チーム紹介でtraPの紹介をしたら、traPにいる人や、TypingWarが好きといって話してくれた人がいました。

会場からは30分くらいかけて歩いてホテルに行きました。
Atcoder Regular Contestがあったので出ようか悩んだが、シャワーを浴びていたら21時を過ぎていたので、文系の課題をやることにした。

課題も終わりのんびりしながら、終わった後のARCの問題を読んで、考えていたらいつの間にか寝ていた。

2日目 - コンテスト前

朝は6:45の起床に成功した。
Twitterをみたらnariさんが「おきた」とツイートしていたのでいいねを押したら、ninjaさんも押していたので、よくわからないところで起床確認が完了した。

まだ完全に覚めきってない頭で朝ご飯を食べていたので、ほんとに2時間後にコンテストするんですか？という気持ちになっていた。

コンテスト会場につくと、また英語を話さなければならず、辛かった。

コンテスト

開始直前

とりあえず、ninjaさんにABあたりを解いてもらい、nariさんに解ける問題とヤバ問を早めに把握してもらおうと思い、PCの環境設定係をすることにした。

開始直後

PCの環境設定として、

capslockの無効化
alias g++="g++ -std=c++11 -static"
ワークスペースの有効化
.emacs, Makefileの作成

をおこなった。ここでジャッジシステムへのログインもやるべきだったのに忘れてしまった。

終わる頃には、ninjaさんがAを解けた感じで、Bは意外と面倒らしいと聞いた。

0:10 - 1:15

ABCは読むつもりがなかったので、他の人に任せて、Dから読んでいった。
Dを開くと、幾何が見えたので一瞬で閉じ、Eをみると、DPですねという気持ちになった。
ある程度は紙実装して、PCの空きを見つけながら実装していったが、 $k$ の存在を忘れていたり、不等号をミスしたり、初期化値を忘れたりで、いろいろとバグらせてしまった。
バグらせなければFirst Acceptを取れていたので、少しもったいなかった。

B問題はそんなことをしているうちにnariさんが解いていた。

C問題もすこしバグったらしいが、Eのバグ修正しているあいだにバグに気付いたらしく、E問題をAC後に、PCを変わったら、すぐに修正して投げて通っていた。

コンテスト中は、Eを通していたものの簡単枠のABCに時間をかけすぎている感じがしていたので、辛いな〜と思っていたが、実際には、1:30経過時に4完しているチームは、他に3チームしかいなく、この時点でABCEを解いているのは結構良かったらしい。

1:15 - 2:05

Eを通したのでF以降も読んでみるが、Fは英語が読めず、Gは幾何だったので、Hを考え始めた。Fはnariさんが分かったらしく、橋列挙が必要ということでライブラリを渡した。少し考えてもHの解法がわからなかったので、Iを読むと証明はできなかったがそれっぽい解法が思いついた。
数チームくらい通していたので、大丈夫だろうと思って解いたら通ったのでラッキーだった。

順位表を見てみると、周りには東大がいっぱいで、このあたりから上位を狙えるのでは？という気分になっていた。(あまり良くない)
AC状態をみると、ABCEFGIしか解かれていなく、すでにFGには取り組んでいたので、FGが解ける問題であるといった情報しか得られなかった。

2:05 - 3:50

情報もないので、H,J,Kあたりを考えていた。

nariさんとninjaさんがF,Gを結構詰めていたが共にバグっているらしく大変そう。

H,J,Kに手が付けられないので、nariさんと一緒にFのバグをいろいろ考えていた。

nariさんがナイーブ解を書いて比較をし始めたら、かなり小さなグラフでも異なる結果がでていて、1->2と2->1の辺があるときにバグっていることが分かる。

よくよく考えると、橋列挙ライブラリが多重辺に対応していないのでは？？となり修正したが、それでも異なる結果が出ていた。

そんなことをしていると1位のチームが全完まで残り2問になっていた。

いろいろと考えてるうちに、ninjaさんが、Gのバグを修正して通して、これで6完

そんなこんなしているうちに1位のチームがもう1問通し、最後1問になっていた。

Fは比較していたナイーブ解が間違っていたらしく、それを直すとナイーブ解と同じ結果になった。それと同時くらいで1位のチームが最後の問題を通していた。横目にその様子を見ながらnariさんが提出すると通り、ここで7完になった。

ライブラリでバグを生んでいて申し訳ない。

この時点で順位表を見てみると、4位で、さらに東大を無視すると、下のチームにペナルティでは負けそうにないので、8完するチームがなければ東大を抜いて2位であることに気づきWFにいける可能性があるのでは？と話していた。

3:50 - 5:00

虚無

実際には、Dが平方分割で通らないかなとか、Kは後退辺の性質を上手く使えばいけそうと考えていたがどれも解法に結びつかず、何も提出せずに終わってしまった。

コンテスト終了後

順位表を見ると、8問目まで提出しているチームが無かったので5位が確定した。

アリーナを出て話していると1位のチーム方(DEGwerさん)が来て、ソウル大学もメダル枠らしく、メダル枠を除くと1位であることを教えてもらった。WFが確定っぽい話もされたが、急すぎて困った。(実際どうなのか...)

表彰式

いろいろな人の話が終わると、有名なYES/NOがはじまった。
ninjaribatonは凍結後に提出をしていないのでYES/NOには参加できなかった。
10位からはその場で立つように言われていて、4位まではその形式だろうなと思っていたら、前に来てと言われてしまい、前にいくと5位で $29$ 賞と、メダルがもらえた。5位でメダルがもらえたことに違和感を覚えながら、席にもどり、メダルをよく見るとTHIRD PRIZEと書いてあって、間違えてる？と思って焦ったが、大学別順位だったらしく、2位のチームに申し訳なくなった。

MEDAL
3位のメダルと5位の賞状

懇親会

懇親会は、食事もあったが周りに企業のブースもあり、人と話したり、企業のブースを回っていたらかなりの時間を消費してしまった。

懇親会でも企業賞がもらえた。企業賞や企業のブースで物をもらう度に持ち物が増えていき大変だった。(1位のチームはそれ以上に大変そうだった)

最終的には、3つも袋をもつはめになり、大量の手荷物のなか家に帰ることになった。

prize
副賞や企業のブースで貰ったものたち

まとめ

本当に、今回の大会は、順位的に見るとできすぎとしか言えない順位をとってしまいました。WF参加チームに選ばれる可能性がかなりあるらしい。それでも、奇跡的なひらめきで難しい問題を解いた感じはなくて、メンバーがそれぞれ解ける問題を解いた形な気がします。
全体的な成績は良かったですが、自分は2:02にIを通してからは、座っているだけで、Jは問題内容的に自分の担当のような気がするので解きたかったですね。それ以外にも、ライブラリの整備やある難易度を超えた問題には全く手が出せてなかったりなど、反省点は多いので精進していきたい。

明日の担当は、OrangeStarさんとgotohさんです!!