Google Code Jam 2010 Round3

Google Code Jam

ここに来るまでギリギリの展開ばかりだったのに…。というRound3。
どっちにしろ、コンテスト中は精神的にギリギリだったわけですが。

  • -

A : De-RNG-ed

問題：桁数がD以下の素数Pと，P未満の非負整数S[0]を選び，非負整数A，Bを用いてS[i+1] = (A*S[i]+B) mod Dにより乱数列Sを生成する．
生成した乱数列から連続するK要素が与えられるので，次にくる値が予想可能ならその値を出力し，不可能なら"I don't know"と出力する．

  • smallは1≦D≦4，largeは1≦D≦6。あとの条件は共通でKが10以下。
  • とりあえず，AもBもP未満の数になる。
    • あれ，smallとか全探索すれば良くね？と思ってTLEにより1WA。
    • P≦10000なのにO(P^3)が間に合うわけないだろう…。
  • 冷静に考えれば，Aを決めれば2つの要素を使ってBが求められる。
    • S[i+1] = (A*S[i]+B)%D だから，B = (S[i+1]-A*S[i]+D)%D
    • これならO(P^2)で出来る！と思って書くもIncorrect。
  • こんな時こそ落ち着いて問題文を読み直してみる。
    • S[0]がP未満という条件にここで気付く。
    • そりゃそうだよね…というわけで修正し、無事にCorrect。
    • Round3とか点数取れるのかな…と本気で心配していたので一安心。
  • largeはとりあえずスルー。
    • そして、そのコンテストを通じて俺に解かれる事は無かった…。

C : Hot Dog Proliferation

問題：x軸上の整数座標にホットドック屋が点在していて、2店以上が競合している座標もある。そこで「2店以上存在する点xから2店を選んで，1店を点(x-1)に，1店を点(x+1)に移動」という操作で2店以上が存在する座標をなくす時、必要な操作の最小回数は？

  • 例えば，
    • [0, 0, 2, 1, 2, 0, 0]
    • [0, 1, 0, 2, 2, 0, 0]
    • [0, 1, 1, 0, 3, 0, 0]
    • [0, 1, 1, 1, 1, 1, 0]
  • みたいな感じ。
  • 座標は絶対値で100万以下で、smallは店数の合計が200以下，largeは店数の合計が100000以下。
  • smallすら分からないぞ…探索するにしても状態数がやたら多そうだし…。
  • 規則性があるのかな…と思い、紙に書いて色々試すも分からず。
  • ぬぬぬ…2店以上が競合する場所を左から貪欲に処理でもしてみるか…。
    • 紙に書いた時は適当な順で操作してもステップ数が変わらなそうだったし…。
    • というわけで、苦し紛れにコードを書いてみたらsmallが通った。
  • largeは歯が立たなそうだったので後回しに。
    • そして俺に解かれる事は(ry

B : Fence

問題：N種類の長さの棒をたくさんつなぎ合わせて長さLにする問題。作れるなら使う棒の最小本数を、作れないなら"IMPOSSIBLE"を出力する。

  • Nは100以下、Lは10^10以上10^18以下で，smallは棒の長さが100以下、largeは100000以下。
  • 見当もつかねぇ…という事でいろいろ迷走して、とりあえず1WAを喰らっておきました。
    • smallのCorrect版コードにlcmとかgcdとか残ってるのはその名残。
  • いろいろ考えた結果、以下の結論になりました。
    • 棒の長さをB1, B2, …，BNとして，BNが最大の長さの棒とする。
    • Lが棒の長さに比べてやたら大きいので、とりあえず長さBNの棒をいっぱい使うと良さそう。
    • 問題は一番長い棒だけでは長さLに出来ないとき。
    • で，DP[i]：長さをBNで割った余りがiになる棒を作るためのコスト
    • として以下のように計算をする
      • DP[0] = 0 : 初期条件。長さBNの棒だけで作れてしまうので追加コストは不要.
      • DP[i] = DP[(i-Bj)%BN] +1 (i-Bj ≧ 0) : 長さiの棒に長さbjの棒を加える
      • DP[i] = DP[(i-Bj)%BN] (i-Bj ＜ 0) : 棒を加えるけど、長さBNの棒が1本不要になるので帳消し
    • これを計算してやれば、L/BN + DP[L%BN]が答えになる。
    • DP[L%BN]が初期化した値のままなら"IMPOSSIBLE"と出力。
  • まずは適当にこの計算を書いてsmallを通す。
    • BN回くらい硬貨問題っぽいDPを回せば良いだろ…という事でO(BN^2 N)で。
  • Largeどうしようかなと思っていたところ、急に配列DPの関係が有向グラフに見え出す。
    • あれ…この配列の値ってDijkstraで計算できちゃう…？
    • これならLargeも…？と思って書いてみるとsmallに提出したプログラムと答えが合う。
    • 提出してみたところ、無事にB-largeが通りました。
  • -

結果 /ox/oo/ox/xx/ 39pt, 72位
まぐれ当たりっぽい部分もありつつ、何とかlargeも1つ通せて大満足な結果でした。
これまでの回は悔いが残る部分もありましたが、今回は出来るだけの事ができた気がします。
やっぱり上位層は凄いなぁ…とも思いつつ、
初めて挑戦してみたGoogle Code Jamでしたが良い気分で終える事ができました。