Google Code Jam 2010 Round 1A

Google Code Jam
  • 午前4時過ぎまで研究室で作業
  • 帰宅して就寝，午前8時半起床
  • 10時からGoogle Code JamのRound 1A
  • ＼(＾o＾)／　←今ここ
  • -

A : Rotate

問題：ボードを時計回りに90°回転したとき、一直線上にRまたはBがK個以上並ぶか判定する

  • 眠い・・・でも英語読む・・・分からない・・・。
  • 盤面を90°回転するチートが使えるところまでは分かったけど。
  • Join-Kって何をするゲームなんだろう・・・？
  • なんて事を考えているうちに20分経過。その辺でついに題意を把握。
  • 実装ゲーか。頑張って書く。サンプル通ったのでSubmit。
  • Incorrect・・・だと・・・？
  • どっかの判定が怪しいんだろうけど，探すのが面倒。
  • テストデータはあるので，90°回転した盤面を出力してチェックすれば良いか。
  • と，30分かけて100問全てチェックするも怪しい出力が見つからず。あれ？
  • ・・・良く見ると"Neither"を"Neigher"とか出力してる。サンプル通ってないじゃないか。
  • 直して再提出。Correct。
  • だからサンプルはしっかりチェックしろとあれほど(ry

B : Make it Smooth

問題：配列の挿入・削除・値の書き換えにより隣り合う要素の差がM以下になるようにする

  • 挿入のコストがI，削除のコストはD，書き換えコストは元の値と書き換え後の値の差の絶対値
  • 最小コストでの書き換えか。挿入・削除・置換とか編集距離っぽいしDPか・・・？
  • 配列の値が0以上255以下というのも，きっと使うんだろう。
  • DP[i][j] : i番目の要素までを使い，最後の要素の値をjにして条件を満たす配列を作るためのコスト
  • にすれば何とかなるような気がする。
  • DP[i][j]の条件を満たすような配列の作り方を考えると…
    • DP[i-1][j]の状態からi番目の要素をコストDで削除
    • (i-1)番目の要素まで全てを削除し，i番目の要素の値をjに書き換える
    • i番目の要素の値をjに書き換え，DP[i-1][k]の状態からM間隔で要素を挿入する
  • 以上の最小値を取れば良い気がする。
  • 紆余曲折を経てsmallは通りました。
  • largeは2番目の条件の実装ミスで死亡。なぜsmall通った・・・。

C : Number Game

問題：2つの数(A, B)を使ったゲームNumber Gameで，A1≦A≦A2かつB1≦B≦B2を満たす(A, B)のうち先手必勝なものは何通り？

  • Number Gameとは・・・
    • 自分のターンでは，任意の正整数kを用いてAをA-kBで書き換えるかBをB-kAで書き換える
    • 2人で交互にこの操作を繰り返し，0を作った方の負け
  • A2とB2の上限が100万とかあるので，DPするだけじゃないのは確か。
  • だけど、残り30分しかなかったのでとりあえず小さい範囲でDPして規則性を探してみる。
  • (i,j)に対してj≦aiまたはbi≦jなら先手必勝となるai，biが存在しそうな雰囲気。
  • 小さい範囲だと，biの値は{2, 4, 5, 7, 9, 10, 12, 13, 15, ... }となってる。
  • うーん・・・。時間無いし、とりあえず数列検索に突っ込んでみるか・・・。
  • どうやらceil(i*(1+sqrt(5))/2)らしい。他に手も無いしこれで実装してみる事に。
  • (i,j)が勝ちなら(j,i)も勝ちなので，たぶんbiを使ってaiも計算できる。
  • 各iに対し，B1≦j≦B2のうち必勝となるjの数はaiとbiを使って定数時間で計算できる。
  • 書いた。サンプル通った・・・だと・・・？
  • あと3分。small出してみるか。Correct・・・だと・・・？
  • largeも出しましたが落ちました。死因は答えをintで計算したことによるオーバーフロー。
  • だから最悪ケースの検討はしっかりやれとあれほど(ry
  • しかし，ceil(i*(1+sqrt(5))/2)で計算できちゃうのか・・・。
  • 理由が良く分からないので後で考えてみよう。
  • -

結果 /oo/ox/ox/ 51pt, 459位

グダグダでしたが，何とか次には進めそうな雰囲気です。
次までにもう少し練習しておこうと思います。