ICPC2015 国内予選参加記

チームnegainoidoで昨年と同じメンバーのflowlightさん, Tailedさんと参加。
8問中7問解いて、全体1位をとれました。

解いた順番とだいたいの時間は

  • A 7分
  • B 13分
  • C 20分
  • D 61分
  • F 96分
  • E 123分
  • G 162分

でした。

始まる前のチームの戦略としては、

  • 自分が全ての問題を実装する
  • 自分がA,Bを解いている間に、TailedさんはC,DをflowlightさんはE以降を開始直後から考えてもらう

というものを考えていました。

A

一昨年のA問題に雰囲気が似てると思いながら、書きました。
http://pastebin.com/bVRXh8Gd

B

A問題より問題文が理解しやすいと思いました。
http://pastebin.com/SFBjS17A

C

Tailedさんに概要を伝えてもらい、実装しました。
足し算と掛け算を逆に書いてサンプル合わなかったりしました。
http://pastebin.com/LYZWZDub

D

このへんから難易度が急上昇してましたが、flowlightさんがDPを考えてくれたので、実装しました。
何個目の商品、500円玉の枚数、500円以外のお釣りの合計という状態で最小コストを持つDPでした。
お釣りの計算や、使う千円札の枚数などで結構バグりました。
このへんでプリンタがなぜか印刷できなくなってしまい、紙デバッグが不可能になりました。
E問題を書こうとした時に間違ってソースコード消しました。

F

Dまで終わった時点でEの方針が立っていなかったのと、Eが自分には無理そうだったのでFをflowlightさんと考えました。
その間、Gが出来そうと言っていたTailedさんにライブラリを写経してもらってました。
自信は無かったのですが、全域木を片方の会社の辺だけでつくり、最も得する辺を交換していくという貪欲を二人とも思いついたので、
Tailedさんからバトンタッチして実装しました。
解法があっているか分からなかったので、flowlightさんには若干渋い反応をされましたがACできました。
http://pastebin.com/VnSYj8mM

E

自分がFを書いている間に、flowlightさんがEを解いてくれていたので、解法を聞こうとしたのですが、
flowlightさんに書いてもらったほうが早そうだったので、書いてもらいました。
77uのサンプルだけ通らないと言っていたのですが、自分自身でロックしたものをロックしようとすることがあると言ったら、すぐ修正して通してくれました。
http://pastebin.com/QQbLDSit

G

Eを解いた後は、TailedさんにGをずっと書いてもらいながら、自分とflowlightさんでHを考えていました。
すごく長いライブラリの写経でコンパイルエラーを沢山出していたので、キーボードを自分と変わってもらって3人でペアプロしました。
サンプルが丁寧だったので、バグを少しずつつぶしながらACできました。
http://pastebin.com/yaBJNzSi

残り

flowlightさんが最後にロボが集まる場所の候補を絞ってくれたので、最後20分弱でHを実装していたのですが、間に合わず終わりました。
縦棒のチームとは結構激しいデッドヒートを繰り広げていたので抜かされないか冷や冷やしてました。

その他

ひどい詰まり方をする問題がなく、多くの問題が解け、いい順位が取れたのでとても嬉しいです。
チームメイトが自分が解けない問題を解いてくれたので、感謝の気持ちでいっぱいです。

当日は去年の成績が良くなかったのと今年で最後というプレッシャーで胃がキリキリしてましたが、ありがたいことに研究室の先輩に胃薬をもらえたので何とか凌げました。
終わった後、もとチームメイトのpepsin_amylaseさんとy3eadgbeさん(コーチ)に台湾料理ごちそうになりました。