ICPC 2015 日本国内予選

チームchikOkU(@__math,(M2),@ustimaw(M2),@kyuridenamida(B3)の3人)で出てました.

戦犯は大体僕です.

全体9位で通過はしましたが,チームに迷惑をかけてしまって,かなり落ち込んだ予選でした.

--

--

これかなり本心です.実際,3完だとうちから出てる他のチームに負ける可能性が高かった.

あんまり詳細覚えてないので,流れだけ書きます.

コンテスト開始前
  • うちからは4チームいて,同じ部屋で受験する感じでワイワイ.
  • USBポートが足りなくて,USBハブが欲しくなって生協に買いに行くか...と思っていたら,別チームのきひろちゃんがHHKB使わないから貸してあげると言って貸してくれ,HHKBが高級USBハブになった(※).

(※HHKBにはUSBポートが2つあるので,つまり1つだけポートを増やせます.)

コンテスト開始(0分)
  • ネットに繋がる.
  • プリンタで問題文印刷するものの,他の2チームだけはうまく印刷できて,僕ら含めた2チームでキューがつまってうまく印刷できない.
  • その間にまーすさんにAを解いてもらう.
A AC(5~6分)
  • 多分4位くらいでFAとるぞ~と意気込んでいたまーすさんが落ち込んでた.
  • ようやくプリントできたと思ったら,なぜか裏表印刷してしまった.3部は印刷できてないので引き続き印刷したくなる.
  • 仕方ないのでBをまーすさんに解いてもらう.
  • 印刷待ってる間にCを少し読んではあはあなるほどとなる.
B AC (10分ちょい?)
  • はやい.でも問題文はまだ完全には印刷できてない.
  • C書き始めるけど,慌ててて少し細かい遷移条件がうまく思いつかない.再帰でLL(1)のときのように適当にやればいいのは分かるのだけれど.
  • まあとりあえず冷静に脳内でサンプルを動かしてみて動きそうな方法を書く.
C かき上げる(35分くらい?)
  • かなり手こずったし,少しだけバグった(オペレータを'*'だけしか受け付けてなかった)けど,まーすさんの指摘でサンプルが通る.
  • データセットを落としてきて,ちゃんと構文解析完了してるかassertで確認しようみたいな気分になり,assert入れたらassertバグる
  • 焦って5分ほど時間吸われたけど,assert入れるときに変なキー押して構文解析パート実行するコードが消えてたのが原因らしい.修正.
C AC (40分前後?)
  • 順位は悪くはない.
  • とりあえず,ustimawさんにDを書いてもらう.
  • その間にまーすさんとEについて話したりする.しかし,trie木にすると性質がよくなる...等言っていたけど,そもそもうまくデッドロックが発生するイメージをただちに想像できなかったので,「ごめんなさい」する.
  • とりあえずグラフであるFを考える.2日前にちょうどマトロイドを扱う試験があったのもあって貪欲か~?となる.
  • この国内予選,難しすぎるという話をする.
Fかんがえる
  • 辺の小さい順に「残りの辺でグラフを連結にできる」なら追加する貪欲を考える.でも,辺集合からk本のA辺とn-k-1本のB辺を使って連結にできるというやつの判定方法が全く思いつかない.つらい気持ちになる.
  • その間に,ustimawさんがDにハマっていた.
D バトンタッチ (1時間10分くらい?)
  • ハマっているのはやばそうということで,まーすさんと議論して,方針をustimawさんのものと照らしあわせて,少し違ったので僕にバトンタッチしてもらう.
  • 僕の方針,たしかにあっていたのだけど,僕だけ計算量の見積もりを""""一切""""していなかったので,メンバーの忠告を無視してなぜかmapモリモリ使ったダイクストラで書き上げる.バグをいくつか潰してサンプルが合ってさあ提出するぞ~となったらテストケースの実行が終わらない,死.
  • そもそもダイクストラになぜかコスト含んだ状態もたせてた.修正→終わらない・・・死
  • その後適当な改善をしようとするが,クソコードすぎてもうだめ.
D 僕まではまる Ω\ζ°)チーン (2時間くらい)
  • 3完やぞオイ予選落ちするかも...
  • メモ化再帰で書き上げたと思ったらDPの形をしてなくて実行結果がバグる
  • 頭がついてないと言われても仕方ない感じになった.
  • 仕方なくまーすさんが一から書き直してるときに,あとすこしで完成しそうというところで僕のメモ化再帰のコードを修正させてもらう.
  • とりあえず強引に『余ったお金の総額=min(余ったお金の総額,a)』みたいなaを弄るコードを書いて,答えが変化しなくなったら出す感じのコードで怪しいが出させてもらう.a=15000くらい.
D 1つ目のデータセットAC (2時間半くらい)
  • おもいっくそよっしゃああと手を叩くけど,メンバーに冷静に「まだ1つしか通ってないからな」と言われ,冷静になる.
  • 2個目の実行をしているときに,a=15000なのに関わらず,配列を15001でなく10001で取っていることに気づいて心臓が止まりそうになる.
  • でもまあもう仕方ないし実行に成功してしまったので2つ目のデータセットのやつも出す.
D AC (2時間半くらい)
  • なぜ通ったのか当時全く分からなったけどワイワイってなる.神のご加護を感じた.
  • 冷静に考えると1万以上無駄なお金を手に入れる遷移が無かっただけなのかも.
  • まーすが解法を詰めていたというEを書いてもらう
  • その間にFの考察をustimawさんと二人でする.
E 書き上げ (2時間45分くらい)
  • はやすぎでしょびびる
  • まーす「最悪計算量膨れ上がりそうで怖いんだよなあ....実行間に合うといいんだけど」
  • 一瞬で実行が終わる.
  • 提出
E AC (2時間47分くらい)
  • すげえ5完.まーすの力じゃん.
  • とりあえず間に合わ無さそうだけど,Fの嘘方針っぽい怪しい貪欲コードを書く.
  • 当然間に合わずオシマイ.
コンテスト終了 (3時間)
  • うちは9位で通過.賞がほしいからあと1位下がって欲しい気持ちでいっぱいだった.
  • Ishibashi DとEで詰まっていたみたいで悔しくも3完でアジアならずだった.うーむ残念.
  • 他のチームは2完と3完だった.同級生(と英語サークルの先輩?)に即席で組ませたチームが3完しているのはすごい!と思った.2完のチームのメンバーの人も来年は行くぞアジア地区みたいになっていてほしい.
反省
  • 【チームの力】÷【個人の実力の最大値】> 1.0 になっていれば良いんですが,多分0.75くらいにしかなってないのでかなり反省しています.
  • Hを読むのを放棄してしまったのは完全に失敗だったぽく,JOI春合宿の問題文は全部読みましょうの再来になってしまった.
  • アジアがんばります.