日々drdrする人のメモ

今日もdrdr、明日もdrdr

ACM-ICPC 2017 Asia Tsukuba Regional に参加した話

12/16,17に行われたACM-ICPC 地区予選 つくば大会の参加記です。

ACM-ICPC 2017 Asia Tsukuba Regional | 国際大学対抗プログラミングコンテスト2017アジア地区つくば大会

ICPCチームIQ1は今年7月に行われた国内予選を通過することができたので、地区予選に出場しました。
チームIQ1は、自分とちゃっく、kuwa氏の三人からなるチームで、コーチはshimomireさんです。

1日目

エクスカーションとしてJAXA見学があり参加すると答えてたので早起き。7時に起床。
つくばまで移動する間眠すぎて、エクスカーションを希望した数ヶ月前の自分を殴りたくなってた。

集合時間前にはつくばに到着し、ちゃっく達に遭遇。
バスに乗ってJAXA見学した。

この見学の間に昼飯として配布された弁当を食べていた。

午後にはコンテスト会場であるつくばカピオに移動した。ここでkuwa氏と合流した。
チームの受付を行い、名札と黄色(オレンジ?)のTシャツを受け取る。この時コーチであるshimomireさんの名札も含まれていて、コーチが入れなくなってた。

チームの席は最も端っこの席だった。


一通り準備した後、リハーサルの時間になった。
とりあえずPythonC++でのコード提出やclar, 印刷の確認を行っていた。
demoの時は入出力のテキスト(***.txt)があったがリハーサルの時になかったのでそれをclarとして投げていて、その勢いでコンテスト問題に全く関係ない筆記物に関するclarも投げてしまい、完全にIQ1感が出てた。

リハーサル後は歓迎会。🍞とか🍝とか出てた。
歓迎会の途中で各チームが英語でチーム紹介していたが、チームIQ1のメンバーは直前まで誰が話すか決めていなかった。結局ちゃっくが手短に紹介してくれた。

歓迎会後はホテルに移動。同じホテルにチェックインするコンテスト参加者が結構いた気がする。

ホテルに大浴場があったが、なぜかお風呂のお湯が冷めていて、隣にあったサウナにだけ入った。

2日目

7時くらいに起きて、朝食を食べた。
スケジュール的にお昼の時間がなさそうだったので結構ガッツリ食べてた。

朝食後は準備して、8時過ぎくらいにホテルをチェックアウトして会場に移動。

9:30からコンテストが始まった。問題は11問で5時間。

コンテスト中の流れは以下。きちんと流れを覚えていないため大雑把:

  • コンテスト直後、ちゃっくはA, kuwa氏はB, 自分はCを読む。朝のねむみもあってか、C問題の英文を何回も読むもなかなか解釈できず、A問題を通していたちゃっくに問題文解読をお願いする。問題概要を教えてもらい、それを元に考え計算式を思いついて実装するもWA。結果が1未満になる時の出力を考慮していなかったのに気付き、それを直してAC。C問題を考えている間にkuwa氏がB問題を通してくれた。
  • ちゃっくがE問題で困っていたので代わりにE問題を考えてみる。なんかdequeで貪欲にできそうだなと思い、試しに実装するとサンプルが通る。しかし、全てのケースが通るか怪しかったので、愚直なメモ化dfsで正しく計算するプログラムを書いて答え合わせをするとダメなケースがぽろぽろ出てきて終了♨詰んでしまったのでE問題をちゃっくに交代する。
  • I問題をkuwa氏と一緒に考える。この問題で、1つの区間に重なる別の区間の数の計算に悩んでいたので、その計算方法を考える。少し考えたら計算は区間に重ならないものを全部から差し引くことで計算できることに気付き、これをkuwa氏に伝え実装を行ってもらう。最終的にはACになった。
  • その後はちゃっくからF問題の概要を教えてもらい考える。が、聞き方が悪く、各iについて1~iまでの有向辺が反転したグラフだと勘違いしてしまい、無理無理〜〜って感じになってた。その間にちゃっくとkuwa氏がG問題を通していた。その後、F問題は正しくはi番目の有向辺のみ反転するというのを聞いて考え直し、だいたい想定解法どおりの解法にまとまる。ここで橋検出が必要になったが、誰も実装持ってきていないことに気付いたため、とりあえず頭で覚えている実装を行う。この計算であればPython3で大丈夫だと思い実装を行い、サンプルが通るようになるが提出でTLEが出る。PyPy実行のPython2に実装を変更して出すもRE。辛い。
  • F問題がバグりΩ\ζ°)チーンとなった後はちゃっくがE問題の実装を行って提出するもWAで通らず。そのままコンテスト終了。

結果ABCGIの5完。C通してあとはFをバグらすだけのお仕事だった。

コンテスト後はシアタールームの方に移動し、いろんな方のお話があった後、コンテストの結果の発表があった。
チームIQ1は14位になった。
f:id:smijake3:20171218194844p:plain

そして最後は懇親会、いろいろ食べ物がおいてあり、周囲にはスポンサー企業のブースがあり、いろんなグッズがもらえた。

懇親会の途中で企業賞等の発表をしていて、その中でチームIQ1はIBMの企業賞をもらった。

懇親会が終わった後は解散になり、そのまま帰宅した。

3日目

3日目には企業見学があったのだが自分は希望しなかったので、オフトゥンにずっと引きこもってた。

反省等

コンテストの順位としてはまあまあかなと思ったけど、うまく行っていればもう少し解けたかなという気持ちもあった。やっぱり解法が分かったF問題を通せなかったのは悔しい。
ライブラリはきちんと持ち込むべきだと思った。今回橋検出がなくてひどく困ったわけではないが、その他の実装が全く分からないアルゴリズムが必要になった時がつらそうだと思った。