ゆらのふなびと

競プロ, Python, C++

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位なので通りそうだけど微妙な後味

反省

  • 実装力を Yazaten に頼りすぎなので、自分ももっと鍛える必要があると思った
  • 特に「実装寄りの考察力」
  • E の列挙パートで自分が提案した方針はよくなかった
  • AOJ-ICPC の黄色をやっていくのがよさそう
  • アジア地区がんばるぞい

*1:Aのペナルティタイムを短くするため

*2:Pythonで書けばもっとよかった

*3:ここでわざわざ分担しているのは、Dを早く通したかったのと、僕が全探索パートの計算量をよくわかってなかったため