去る土曜・日曜に開催されたGoogle Code JamのRound 1に参加した。去年に引き続き2回目の参加。Round 1Aでたった1問しか解けなかったが、Submit時間が早かったおかげで幸運にも通過。今回はRound 1AのContent Analysisを訳すことで振り返りを行う。
Overview
Round 1はかなり過酷なスタートを切った。始まってすぐに、スコアボードのすべての問題が誤ったsubmissionでいっぱいになった。Problem Bが最初に解かれるまで40分、そしてProblem Cが最初に解かれるまで2時間もの時間がかかった。
終了してからも、largeへのsubmissionのうち相当の数が誤りであることが判明した。そのため、スコアボードの上位では大幅なシャッフルが起こった。
Problem Bで起こった混乱は、問題文が本来あるべき水準よりも明快でなかったことによって起こった。この混乱に我々が気付くのに2時間もかかり、説明のメッセージを流さなくてはならなくなったことをお詫び申し上げる。
最初にすべての問題を解いたのはkrijgertje氏で、残り27分だった。Progbeat氏もまもなくそれに続き2位に入ったが、結局その15分後にMyth氏に抜かされた。その他には誰も全問解くことはできなかった。
上位1000人の参加者の皆様、おめでとう。Round 2へ進める。他の参加者もRound 1B, 1Cと2回のチャンスが残っている。
Problem A
この問題で最初に気付くべきことは、P_DとP_Gは0から100までの値をとることだ。なのでまずは簡単な場合に注意をすることから始めよう。もしこの名もないプレイヤーが累計100％の勝率(P_G = 100)にもかかわらず、今日の勝率が100％でなかった(P_D < 100)なら、明らかに計算機は壊れているだろう。同様に、もしP_G = 0かつP_D > 0なら、計算機は正常でないだろう。
P_D = P_G = 0の場合、またはP_D = P_G = 100の場合もまた簡単だ。この両方の答は"Possible" - これらは、すべてのゲームが同じ結果、つまり全敗か全勝であることを意味する。
ここまででP_G が0の場合、および100の場合を除外できたので、もうP_Gがこれらの値をとることについては考える必要はないというのがコツだ。実際、1日分の正しい勝率を与えることのできる数字が存在すると仮定しよう。ここでその数字は、今日一日で勝った数Wと負けた数Lからなるとする。このとき、累計の勝率P_Gを得るために、例えば、累計の勝ち数が(W+L) * P_G、累計の負け数が(W+L) * (100 - P_G)と仮定することができる。1 ≦ P_G ≦ 99なので、これらの数はそれぞれWおよびLより大きい。よって起こりうる数字である。
このことから、smallデータセットは総当り法で解ける。つまり、Dについて1からNまで変化させ、勝ち数を0からDまで変化させて、そのどれかについて1日分の勝率がちょうどP_Dになる場合があるかどうかを調べればよい。
largeデータセットを解くにはもう少し計算が必要である。問題を解く一つの方法は、勝率P_Dを得るために必要な最小の勝ち数を直接求め、その勝ち数がN以下であるかどうかを確かめる方法である。ここでWを今日の勝ち数とすると、Wが整数であるという制約のもとで W / D = P_D / 100 を満たすような最小のDを求めることになる。
この式からD = 100 * W / P_D を導くのは簡単だ。すると、最小のDを得るためには、この式の右辺が整数となるような最小のWを求める必要がある。それを求めるには、100とP_Dを、その最大公約数（Gとおく）で割る。そうすることで100とP_Dは互いに素になり、WはP_D / Gと等しい時に最小となる。この式を代入して項をキャンセルすると、D = 100 / Gが、プレイすべき最小のゲーム数であることがわかる。
最も簡単な解法は総当り法である。Dについて1からNまで変化させ、そのうちのどれかで勝率がちょうどP_Dになるかどうかを、D * P_D = 0 (mod 100)によって確かめる。ここで、最初の候補Dを見つけるか、またはDがNを越えればループを終了する。一見この解法はO(N)に思えるためlargeデータセットでは時間切れになりそうだが、このループはNの値にかかわらず最大でも100回しか回らない。なのでこの解法は十二分に早い。この単純な解法に早々と気づいたコーダー達は非常に早く解答を提出できた。
