Google Code Jam Japan 2011 決勝

GCJ Online Judge

目標はGoogleから賞金をもらうくらいで。

問題を読むフェーズ

  • A問題
    • なんか見たことのある問題だなあ。冬合宿のHull Marathonっぽい。しかしk大きすぎだろ。
  • B問題
  • C問題
  • D問題
    • らくがきの魔女っぽい。やるだけ？
  • E問題
    • ドラゴンカーブなんてやりたくないです。本当にそうか知らんけど。
  • 全部読んだのでAから考える。

A問題

  • 問題読み直したら角度固定じゃん。と言うことは…。これってJag Day4のC問題(の元の案)じゃん。
    • 一個置いて交互に左右に置いていくだけ。
    • 書いた。submit AC。

C問題

  • Bよりもとっつきやすそう。
    • DPとか出来んのかなあ。分からん。
    • とりあえずsmall通すか。
    • 書いた。WA。WA。WA。なんかワイルドカードマッチの部分が間違ってるくさい。
    • もうSpaghetti Sourceのやつを貼りつけてしまえ。smallをsubmit AC。

B問題

  • とりあえずCは素数とすると…。フェルマーの小定理から、一つ上に行くごとにCが1ずつ減るのか。
    • Cが素数でない場合は？オイラーの定理から考えると\varphi (C)になるのか。
    • じゃあxとCが互いに素だったらメモ化再帰でもすれば解けるな。
    • サンプル一致した。間違ってるけどsmallをsubmit WA。けっこう厳しいな。
    • xとCが互いに素でない場合は？どうせ周期分(\varphi (C))だけ余分に回せばいいだろう。ということでmodで余りを取ったことがあるかどうかのフラグを使って計算してみる。
    • なんか答えが変わった。submit AC。largeもsubmit。

D問題

  • とりあえずsmallを解きますか。
    • 2次元のfieldに入り口の個数とかを記録しながら、上から全探索。一番下まで行ったら全ての入り口に辿りつけるかチェックする方針。
    • 書いたけどなんか答えが合わない。
    • xとyをミスってる箇所があっただけだった。submit AC。
    • C large、D large、E smallだったらD largeが一番可能性がありそう。
    • やるだけ。…よく考えたら、やるだけなんだけど2行分保持しておかないとだめじゃん。おわた。

結果

oooooxoxxx 60点 2:45:14 4位。
賞金をもらうという目標は達成できた。時間差ではないんで3位を狙うには実力が足りなかったということで。