Google Code Jam 2011 Round2

Google Code Jam

この辺からはリアル知人がだいぶ減って寂しくなるラウンド。

  • -

A : Airport Walkways

問題：長さXの直線上にところどころ動く歩道があって、基本は速度Sで歩きつつ、全体でt秒だけ本気出して速度Rで走るとき、直線を進み切るのにかかる最短時間を求める。

  • これ、歩道の速度が遅いところから貪欲に走るだけだろ…。
    • 式を立ててみると、確かに速度が遅いところで走ったほうがお得
  • 開始10分くらいでコードを書きあげてコンパイル。幸先の良いスタート！
    • と思ったらサンプル通らない。どこが幸先良いのか
  • ところどころで歩道の速度足してないとかひどい
    • サンプル通ったので、smallに投げる → Incorrect
    • …(゜.゜)
  • intで割り算してるところがあったので、doubleにキャスト
    • やっとsmallが通ったので、そのままlargeにも投げた

B : Spinning Blade

問題：鉄板から、重心が中心にくるような、なるべく大きいコマの形を切り抜く問題。

  • 部分和を使って尺取りっぽくゴニョゴニョすれば普通にO(N^3)くらいで終わりそう
    • ここでゴニョゴニョを余り深く考えなかったのが、たぶん敗因
  • 100行に迫るカオスなコードが姿を表し、1時間くらいデバッグしてサンプル通る
    • が、不安なので適当にケースを作ったら簡単に撃墜できた
  • スコアボードを見たらTシャツすら怪しい感じだったので、一旦パス
    • Cを読んだあと、とりあえずsmallのみ通して、この問題は終了しました

C : Expensive Dinner

問題：i番目の友達は注文金額がiで割り切れないとアンハッピーという感じの友人がN人くる。友達の来店時に注文がされる回数の最大値と最小値の差を求める問題。

  • 問題読み間違ってて、しばらく無理ゲー…となってた。
  • とりあえず、あと30分でこれのlargeを通せば通過への希望が見えてくる。
  • 全く見えてこないので、小さいケースから考えてみる
    • N=2 : 1->2なら2回，2->1なら1回
    • N=3 : 1->2->3なら3回，3->2->1なら2回
    • N=4 : 1->2->3->4なら4回，4->3->2->1なら2回
  • うーむ…1番目の友達は消すも消さぬも自由ということくらいしか分からない。
  • あとは、金額が来店済みの友人の番号のLCMになるくらいか…。
  • i番目の友達が注文しない条件ってなんだろ。
    • 金額がiの倍数になってるときだから…最終金額を素因数分解してみるか。
    • N=4 : 最終金額は 2^2 * 3^1
    • N=5 : 最終金額は 2^2 * 3^1 * 5^1
    • N=6 : 最終金額は 2^2 * 3^1 * 5^1
  • 各因数について最低1人は注文しないといけないし、最大でも指数人しか注文できない
  • 素因数分解して、(各因数の指数-1)の和が答えか
    • あと、1番目の友達の分で1も足さなきゃダメっぽい
  • とりあえずナイーブにやってsmallが通った！
  • 素因数分解はsqrt(N)まで頑張れば良いことに気づいて無事largeも通った

D : A.I. War

  • いっぱいいっぱいすぎて、存在が目に入ってなかった
  • -

結果：Rank 373 : /oo/o-/oo/--/ Score 56, Penalty 2:31:30


ラスト30分でAしか通ってなかった状態には敗退を覚悟しましたが、
奇跡的に通過枠に滑り込めたので良かったです。
今日は朝の練習から変なバグを連発していたので、
やはりこういう日は気を付けないといけないなぁ…と思ったりしました。