ICPC Tsukuba 2015 参加記 - あなたは嘘つきですかと聞かれたら「YES」と答えるブログ

11/28昼

・チームメイトと秋葉原で合流。
・つくばエクスプレス、椅子が硬いとの噂で、コンクリート並みの硬さをイメージしていたけど、そんなことはなかった。普通の在来線という感じ。
・駅で静岡チームに出会い、着いていく。
・つくばカピオに着く。カピオはラテン語で「財産」
・会場の前でJOIOBの東大３チームがチームメイトを待っていた。
・プラクティス、キーボードの右シフトを押すと「↑」が入力されるバグに悩まされる。多分'_'キーが長すぎるせい。
・Backspaceを押すとEndが入力されるバグもあるらしい。
・という感じで、日本語キーボードの配列がやばかった。（twitterでもめっちゃ見かけた）
・環境はキーボード以外は素晴らしかった。競技者として嬉しい点は、
　・会場が適温
　・チームに与えられるスペースが広い
　・配線等がしっかりしてて、足元に電源スイッチがあってPCが突然落ちるといったことがない
　・windowsじゃなくてlinuxが使える
・JavaChallenge、さすがに２時間かつ提出して無限に待たないとフィードバックが得られないのではなにも作れず。
・紹介文に書いた迷路解いて写真アップしてもらえててうれしい。他にも解いてくれてた人がいてうれしい。

焼肉 pic.twitter.com/iZTOv7PJWo
— 忘れ物に気をつけよう (@hadrori) November 28, 2015

11/28夜

・懇親会、飯がうまい。皆が寿司にかまけてる間に串カツを１通り食べる。
・チームスライドはperyaudoが韓国の空港で作ってくれました。かっこいい。
・宿に向かう。宿の前に焼肉屋があった。
・風呂が混むのは容易に想像がついたので、爆速で風呂に向かう。
・しかし、準急がすでにいてさすがだと思った。
・ロビーとか研修室で雑談をした。
・歯ブラシを忘れたのでコンビニに買いに行く。コンビニ近くてうれしい。
・寝る。

11/28闇

以下闇情報です。反転すると一応読めます。
・全く寝付けず。
・今回に限らず、ICPC前日はいつも寝付きにくいが、今回は特にひどかった。
・事前に「大会どうせ勝てないしどうでもいいどうでもいい、みたいに考えることによって緊張をなくして安眠する」という作戦を考えていたが、見事に失敗した。
・結局３時間くらいしか寝られなかった。一睡もできないのとは大差があるので、まぁ良かった。
・睡眠薬試してみようかなぁ・・・
・もう完全に絶望的な気持ちでツラかった。

11/29朝

・鮭は皮まで食べる人です。（おいしいよ）
・プリンとユンケルを投入する。
・移動してコンテスト
・時間通りに開始されなさそうな気配を感じていたら、時間通りに開始されてびっくりした。

11/29コンテスト

チームメイト

・peryaudo：３年間チームを組んでいる。JOIで知り合ったスーパープログラマ。googleのインターンとか行ってて完全にプロ。きゅうりとは小学生からの付き合いらしく、いじられキャラの素養がある。
・mine：今年からチームを組んだ。高校が同じで、superconでチームを組んだこともある。ごちうさ。

チーム体制

・snuke：メインコーダー。ひたすら解く。
・peryaudo：持ち前の英語力を生かし、主に問題文を読んでもらう。ライブラリを写してもらったり、サンプルを試してもらったりもする。ちょっかいをかけると楽しい反応をしてくれるので、和む。
・mine：精度の高い仕事をしてくれる頼れる仲間。主に環境設定、幾何・グラフ系のサンプルの図示、数式の計算などをしてもらう。複雑な状態を持つDPの問題の遷移の係数を表す14*8くらいの表を埋めてもらったとき、全部合っててびっくりした。
・問題文について：問題文を簡潔に伝えてもらうというのはもちろん重要だけど、制約・入力がdistinctかどうか・問題の細かい設定などを聞いたら答えてもらえるというのも実に助かる。

記録・感想

・開始後はとても穏やかな気持ちだった。
・ユンケルのおかげか、結構眠さとかはなかった気がする。
・いつもは慌てて問題を解いてハマって余計に時間がかかるというパターンが多かったので、今回は冷静にゆったりと問題を解くことにしていた。
・mineに設定をしてもらってる間にAを読む
・これsubsequenceじゃなくない？と思いつつやるだけなのでやる。
・サンプルをダウンロードできるページ情報を得るためにclarを投げる。
・Bから悩ましい問題だなぁと少し驚きつつも、他のチームもどうせ驚いてるだろうと思いつつ解く。なぜかDAGの最長経路問題に落として解いた。
・Cで今回のセットは前半の重さが増していると確信しつつ、冷静にやる。
・D、時間がかかりそうなので飛ばすべきかと思いつつもABCの次にD以外をやっているチームがなかったのでやる。
・E、桁DPを考えるがprod無理じゃね？となるが、2,3,5,7で何回割れるかを状態として持てば良さそうとなり実装する。添え字がやたら多くて笑いながらコーディングする。
・DPテーブルを再利用してもメモリが足りなかった。
・prodをmapで持った方が状態数減るしなんとかなるやろと思いmapに切り替える。
・TLが1秒なのに実行してみると2秒近くかかってあーと思うが、O2をつけたらなんとか1秒に納まりそうだったので投げたら通った。
・あらかじめ積を列挙しといて状態をlower_boundとかでintに変換すれば高速化できそう。
・ここまでずっと５〜９位くらいだったのでこの調子で行けば良さそうと思う。
・会津が強くてびびる
・他のマークしてたチーム（台湾勢、阪大、FCCPC、筑波、九大、京大...etc）に勝っていたのでほっとする。
・Fを聞くが、複雑で少し時間がかかるが理解する。
・少し余裕がありそうだし、少し疲れたのでリフレッシュ目的でトイレに行く。
・トイレ待ち行列に行ったらいつの間にかperyaudoがいて話しかけたら係りの人に怒られた。チームメイトだけどダメか。
・小走りで席に戻ってたら「don't run」と怒られる
・「トイレに行くだけで２回怒られる男」とperyaudoに煽られ続ける
・F、問題さえ読めばC~Eより簡単。
・問題文に乗ってないサンプルのデータが合って、それだけ答えが違った。
・デバッグしてAC
・G、むずそうなのにA~Fを埋めるより先に解いてるチームがいくつかあってビビる。
・H~Kを聞いてみて、Gをやることを決める。
・結構悩んだ末AC。よくできた問題だった。
・「長さがhogeの回文」ではなく「長さが最短な回文」であることが重要であることに気づくのに時間がかかった。
・解かなければならない問題は全部解き切ったので少し休憩をしつつI,Jあたりを考える。
・残り45分くらい、そろそろどれに取り組むかを決める必要があった。
・H、Jは時間的に無理そう。
・Iでなんらかの嘘解法を生やして枝狩りとかを入れつつ提出しまくるというのも魅力的な選択肢。
・Kは簡単な場合はCFで最近見たなぁと思った。
・残り時間的にはIかKだと思ったけど、台湾がKを解いていたのを見てKにする。
・嘘解法を生やすも、撃沈。
・終了...しなかったので暇を持て余す。
・周りを見渡して凍結後に増えた８完がいないことを確認する。
・阪大チームが延長戦でAC出してたのが楽しそうだった。

コンテストまとめ

・過去の参加経験を生かして「冷静」を実践できたのはよかった。
・持てる力の80%は出し尽くせた（bestを尽くせなかったという意味ではない）かなと思う。これ以上出そうとするとハマる確率が上がって安定しないので後がない状況では最善の戦略だったと思う。
・結果は8位、大学別6位でした。
・メダル枠と別地区を除くと、NTU→Aizu→Keioなので、WFの希望は残っているのではないかなぁと思う。Aizuのシンガポールでのご活躍とCJ先生に祈るしかない。
・＋１完がなかなか難しいんだよなー。今回は残り時間が少なかったから仕方ない気はするけど。
・まぁそれでも嘘を並べれば想定解でなくてもうっかり通ってしまう可能性があるかもしれないタイプのI問題を選択した方が期待値は高かったかなという反省は少しある。
・今年は結果を出したかったので、それなりの結果を出せて良かったです。
・ペナルティ0なの、すっごくないですか？

11/29昼

・解説、スケジュールの伝達ミスで巻きでやってしまったっぽくて、かなり雑だった。でもなんとなくどんな感じかは分かった。
・Java Challengeについて（負なので反転）：Java Challenge作られた方、去年４回も問題を使い回していた方なので非常に印象が悪い。今年は使いまわしではなかったので良かった。しかし、ローカルでテストできない上サーバのレスポンスが激遅だった点、IDとかが0-indexedなのに与えられる座標がどうやら1-indexed（問題文に書いてない）だった点は残念だった。
・Java Challengeがグダグダになるのはいつものことだし、それが面白いってところもあるので楽しかった。メインコンテンツでもないしまぁ多少はね。お疲れ様でした。
・謎の空白時間。
・秋葉さんのカメラから逃げる遊びをしていると、よすぽが素材としてのプロ意識を発揮する。
・表彰式。プレゼントの中身が気になる。（クリスマスはちょっと早くない？w）
・Dreadnoughtまじで圧倒的だったなぁ。あと、風船22個を阻止してしっかり9完したIIIlIIIllIIlIlIIllIlIllllllIIIもさすがだった。
・IIIlIIIllIIlIlIIllIlIllllllIIIがJOMANDAしてた。参考：

J O M A N D A pic.twitter.com/lRlBSoRipN
— おめ (@omeometo) November 14, 2015

dic.nicovideo.jp

11/29夜

・閉会パーティー
・皆んな大好きK理事長の乾杯音頭
・料理は今日もわりとうまい。焼きそばが二種類あるのが謎だった。
・googleブースの謎解きがハイクオリティだった。
・ヨーヨー楽しい。
・社会人のいろんな方と話した。
・例の数式の会社の社長さん、SFCの先輩らしい。（ちなみにここでperyaudoがバイトしてたらしい）
・２つくらい企業賞をもらう。やったぜ！！
・yahooからもらったアダプタkit（しかもmac高速充電）が嬉しかった。