ICPC2017 国内予選 参加記
作戦
- ICPC 国内予選では、問題が紙で届くまで 1,2 分かかるかつ 1 チーム PC 1 台という制約があるので、コンテスト開始直後はディスプレイに問題文とコーディング画面とを別のウィンドウで表示して作業することにした
- ratea: テンプレを打つ→問題が紙で届いたら A を読む
- yurahuna: B を読む
- Yazaten: C を読む
- ratea は解法がわかったら yurahuna に説明する→大丈夫そうなら ratea は A を書く
- B, C の順で解く
- D を考える
- あとはよしなに
本番
- プリンターのトラブルで、印刷が届くまでに時間がかかりそうだったので、戦略を以下に変えた*1
- ratea: A を読む
- yurahuna: B を読む
- Yazaten: テンプレを打つ
- 作戦では ratea は A の解法を思いついたら僕に話すことになっていたけど、代わりに（問題文が届かなくてフリーな）Yazaten が聞く役をやってくれた
- ここら辺特に何も相談してなかったけど Yazaten がうまく立ち回ってくれて助かった（5年目の経験ゆえか）
%%%
- ratea が A を書いている間に僕は B を読む
- 問題文がややこしいので慎重に読んだ
- 文字列をダブルクオーテーションマークで分けてよしなにすればよさそう
- ratea が A を通したので B の実装に取り掛かる
- Yazaten が C++ の split 関数をライブラリとして持っていたので、借りて AC
- 他のメンバーのライブラリを把握しておいてよかった*2
%%%
- ratea から D 問題の内容を聞く
- ratea はいつもサンプルの図を描いておいてくれるのでとても助かる（おかげで今回もすぐに内容がわかった）
- n*m <= 500 という制約があるのでどうせ bitDP するんだろうなあと思ったけどよくわからず
- 考察していると、n <= m のときは 2n 全探索で解けることがわかる
- m < n のときは……と考えていたら Yazaten が C を通してやってきたので D の進捗を話す
- 話していたら bitDP 解法らしきものを思いついたので伝える
- いけそうだねとなったのでやる
- 計算量が不安だったけど†二分（にふん）探索†の精神でやる
- 僕が bitDP パート、Yazaten が全探索パートを書くことに*3
- 2人で順番に書く
- サンプルが両方の解法で合うことを確かめる
- サンプルが合ったのでテストケースを落として実行
%%%
- Segmentation Fault
- 思考が停止する
%%%
- bitDP でメモリ取り過ぎなのかなあという話になり僕が bitDP パートを配列を使いまわすように書き換える
- せぐふぉが取れない
- Yazaten の発案で入力のどのケースでせぐふぉってるのか見ることに
- n<=mなので全探索パートでせぐふぉっていることがわかった
- 全探索パートのコードを読むと、添字がおかしいところを発見
- 直す
- せぐふぉが取れた！！
- ケース 1 通った！！！
- ケース 2 通った！！！！
- AC！！！！！！！！！！！
%%%
- この時点で 30 位ちょい(0WA)だったので、いけそうだけどもう1問通したい気持ちになる
- E と F の説明を ratea から聞く
- E は構文解析、F は考察ゲーっぽさを感じる
- 精神に余裕がないと考察ゲーには手を出しづらい
- Eをとる
- yurahuna「入力の文字列の長さが16以下なのでvalidな論理式を列挙してもそんなに多くならないでしょ」Yazaten「ほんとかなあ」
- Yazaten が変数のない論理式を評価する関数を作る
- yurahuna は列挙パートを考える
- Yazaten がガリガリ実装してくれるが間に合わず終了
- 35位なので通りそうだけど微妙な後味
