Google Code Jam 2011 Round1A

Google Code Jam

この週末は地味に予定が入っていたので、
1Aで通過しておきたいなーという感じでやってみました。
問題概要がだいぶ適当なのは仕様です。

  • -

A : FreeCell Statistics

問題：今日はNゲーム以下を遊んで勝率がちょうどPD％，過去の戦績と合わせて勝率がちょうどPG％になった。こんな事はありえるのか判定する問題。

  • まず0%と100%は適当に例外処理しちゃう。
  • そして、ちょうど1〜99%になるゲーム数Dについて考えてみる。
    • まぁ，Dが 100/gcd(100, PD) の倍数なら丁度PD%にできるよね…。
  • なのでNが 100/(gcd(100, PD)) 以上ならちょうどPD%が実現できる。
  • あとは、G>Pだし、PG%は適当な感じで実現できる。
  • N≦10^15なのに、なぜかNをintで読んでてlargeを落としました。

B : The Killer Word

問題：Seanを文字列ゲーでフルボッコにしてキャンディーの恨みを晴らす問題。

  • ぼくのトラウマTwenty Questionsを彷彿とさせる。
    • というか同じ感じで解けるんじゃね。
    • ちなみに、当時は問題文を盛大に読み間違ってて鬱展開になった。
  • 適当にDFSでシミュレーションする。
  • 文字を指定したときにどこがオープンするかを文字列ごとにビットで持っておく。
  • と、各深さでの分類作業がO(n log n)くらいでできそう。
    • 残ってる文字列リストをオープンビットをキーにしてソートする感じ。
  • 深さも最大26なので、いけそうな気がした。
  • 書いてみたら普通にsmallが解けた。
  • 覚悟を決めてlargeもやってみたら実行に1分半かかってちょっぴりドキドキした。

C : Pseudominion

問題：山札からカードを引いたり、点数を増やしたり、ターン数を増やしたりできるカードを順番に使って得点を最大化する問題。

  • 上手いこと考えれば先頭から処理できるに違いない…とかしばらく考えてた。
  • そして、俺の苦手な超絶DPだと思い始めて苦悶し始めた。
  • 時間がなくなってきたので、とりあえずsmallだけ考えてみることに。
  • カードを引く枚数cが、0か1の2通りだけ。
  • まぁ、ターン数が増えるカードはとりあえず使っておいて良い感じ。
  • ターン数が増えるカードを使い切ったあとは…
    • ターン数分、点数が高いカードを貪欲に使う
    • c=1のカードを1個使って様子を見る
  • これ、それぞれの場合をシミュレートするだけじゃね…。
  • 使用済みフラグの更新を忘れたり、+と-を間違えたりしてだいぶハマった。
  • 最終的にはsmallだけではあるけど通せたので良かった。
  • -

結果：Rank 36 : /ox/oo/o-/ Score 51, Penalty 2:18:12

だいぶ凡ミスをやらかしてしまって残念な感じではありましたが、
問題が難しかった影響か、順位はだいぶ高めでした。
次あたりはこういうミスが命取りになりそうなので、なくしたいところですが…。