Google Code Jam 2017 Round 3

通過しました。
初のGCJ決勝進出です。
GCJは現時点での第一目標だったのでとても嬉しい。
次はTCOかぁ、きっつい。

今回はどれも解法がすらすらと分かったので、GCJと相性が良いのかもしれない。
（けど謎の問題（sortアルゴリズムを推測せよとか、乱択とか）とか強実装とかが出てくると多分苦手）

戦略的にも最適に動けていたので、かなり理想的なパフォーマンスだった。
流れとしては、

  • SubmissionsとTop Scoresはちらちら動いて邪魔だし、焦りの原因になるので閉じておいて必要な時だけ見る
  • とりあえずAは解いておく
    • 逆向きに探索できるなぁとなる
    • 状態数を減らしたい
    • 前の状態が存在する条件＝合計がL以下
      • そういう状態は18C9しかなくて余裕
    • 前の状態が存在しないのは探索せずに数式で計算する
      • L!から種類iがCi個ある時にCi!で割っていけば良くて、解けた
    • small時点で24位だった
    • largeはとりあえず保留するスタイル
      • 最大ケースが明らかに100000000で、これが爆速だったので通るだろと思う
  • とりあえずBも読んで少し考える
    • サンプルを見ながらサイクルにそって加算する感じだと思う
      • なんで負が出てくるのという違和感はあった
    • 他のサンプルを見るとサイクル（有向）がないのにOKな例がある
    • ある辺にx流すのと、逆辺に-xを流すのは同じだという考察
    • 無向グラフで考えた方が良さそう
    • サイクル基底っぽい
    • DFS木を書くと分かった
      • 後退辺に1を割り当てて、対応する木の区間(?)にも+1してやればいい
    • 非連結なケースを忘れたのと修正ミスで2WA
      • 出力をもうちょっとちゃんと確認すれば少なくとも2つ目は防げたし、これが今回唯一の反省点
    • largeは保留
  • Bをさらっと解けて有利になったという実感があったので順位表を見てFinishまでの道のりを確認する
  • D smallが簡単らしい
  • C smallもまぁまぁ解かれてる
  • とりあえずDを読んでlargeは捨てるのが正しそうだと思いつつsmallを解く
    • FAが11分台だったので実装も大したことないはずと考える
    • 小さいやつから伝播させていく感じの貪欲でいけそうとなる
      • 小さい数から見ていけば下限制約は保証できるので、うん正しそうという感じ
    • 通る、調子が良い
  • C-smallをやる前にlargeたちを送っておくかを考える
    • C-smallは必要そうな気配を感じるし、少なくともC問題文読んでからにするかとなる
    • もしlarge提出でトラブルが起きたら焦ってCの問題文長めだしテンパって読めなくなるのが想像できるし
    • C-smallやるだけ感があったのでやる、通る
  • この時点で通過をほぼ確信したので、largeたちをドキドキしながら出す。
  • のんびりC-largeでも考えるかーとなる（実際にはこれが解けないと通過できなかった）
    • 有向グラフのオイラー路なので、頂点ごとに独立にやっても勝手にオイラー路になるやろと思う
    • すぐできるし余裕もあるからと、とりあえず実装してみたけどsmallと合わない
    • 連結性が崩れる場合があることに気づく（他にもバグがあった（おい））
    • MSTで解けるなぁ、なんだこの絶妙な問題はとなる
    • 合わない
    • 始点を特別処理しないと行けないことに気づく
    • 提出（C-largeちょっと気が緩みすぎ感はあったか）
  • お祈りフェイズ。Dはさすがに無理だし、暇
  • ペナルティ差で準急に微妙に負けていた(◞‸◟)
  • 仕方ないからD-largeを綺麗に実装できないか考える
    • ボロノイ図みたいになるのはすぐ分かった
    • bounderyが８種類の直線で表せてそのandを取った領域内の値を頑張って計算したい
    • 始点から距離を１ずつ増やしていって距離が同じマスたちを一括で足す感じをイメージする
    • bounderyに引っかかると、増えなくなる方向が出てくる
    • 右下、右上、左下、左上と真上、真下、真右、真左の８種類の領域に分けてみると、bounderyにぶつかった時に増えなくなる分が割と簡単に求まることが分かる
    • 有限時間で実装できる気にはなったから実装を始めたけどさすがに間に合わない
      • （追記）後で気づきましたが、領域凸にならない場合あるやん！（sample1とか）これは実装不能ですね。
  • 終了、全部通って12位通過、めっちゃ嬉しい

GCJはいかに冷静に解くべき問題を取捨選択するかが重要で、これさえ間違えなければ解けるべき問題さえ解ければ割と通れる。
昔の自分だったら絶対やってないんですが、素早く書けそうなC/Dのsmallをさっさと回収するとだいぶ心に余裕が生まれたりもするので重要な気がする。
ストレステストにも使えるし、ベースの解法の確認ができることもあるし、無駄ってことはないと思うし。
GCJの戦略とかはりんごさんのツイートを見ると参考になると思います。
例えばこれとか。

おまけ：コンテスト前の準備
昼ごはんは慎で贅沢に天ざるうどんを食べた。
くっそうまかった。やっぱりこの店最高すぎる。（ちょっと遠いけど）（大体並んでるけど）
2014の問題を解いてたら眠くなったので仮眠を取った。
晩飯はがっつり食べずに、プリンとメロンパンと高千穂コーヒー牛乳で済ます。
念のため栄養ドリンクを買ったけど飲まなかった。
コンテスト前にプリンを食べるのはおすすめです。