Google Code Jam 2013 Round 1A
毎年恒例、今年もGoogle Code Jamに参加しています。
A-small, A-large, B-small, C-small-1を正解。
669位でRound 2進出です。
いつもRound 1Cまで粘って辛うじて通過しているので、
1Aで通過したのは初めてでテンションが上がりました。
A問題が得意分野でlargeを通せたのがよかったようです。
A. Bullseye
まずは法則を見つけるため、1本目、2本目、3本目…のリングの面積を求めてみます。
1本目(n=0): π(r+1)^2 - πr^2 = π(2r+1)
2本目(n=1): π(r+3)^2 - π(r+2)^2 = π(2r+5)
3本目(n=2): π(r+5)^2 - π(r+4)^2 = π(2r+9)
1,5,9...の部分をkとすると、k = (2n+1)^2 - (2n)^2 となる気がします。
(てか4n+1なのですが、競技中はこれで進めてました)
したがって、π(2r + (2n+1)^2 - (2n)^2)と一般化できます。
1mlで面積πを塗れるそうなので、πで割るとペンキの必要量になります。
n+1本のリングを塗ったときのペンキの必要量は、
Σ[x=0→n](2r + (2x+1)^2 - (2x)^2)
= 2r(n+1) + Σ[x=0→n]((2x+1)^2 - (2x)^2)
となり、後半のΣの部分をWolframAlphaに突っ込むと、
= 2r(n+1) + (n+1)(2n+1)
となります。
これで、n本の場合のペンキの量がO(1)で出せるようになりました。
あとは、ペンキの量がt以下になる最大のnを求めます。
tの範囲も大きいので、二分探索で求めます。
nの範囲は適当に0 〜 2*10^18としても2^60くらいなので、60回くらいのループで求まります。
C. Good Luck
テストデータのすべてに正解する必要はなく、指定された個数以上合ってればいいという珍しい問題です。
去年の乱択といい、確率問題がよく出ますね。
small-1は、Maryamが選ぶのは2〜5の数字を3個なので、
組み合わせの数はH(4, 3) = C(4+3-1, 3) = 20通りです。
Hは重複組み合わせです。今回ググって初めて知りました。
で、3個の数の部分集合は2^3 = 8通りです。
なので、数の集合とその部分積をすべて列挙しても20 * 8 = 160要素のテーブルで済みます。
テーブルを作ったら、与えられた積になり得ない数を削除していきます。
例えば、積が10なら、3 3 3の部分積は10になり得ないので、3 3 3を削除します。
こうして残った数のうち、適当に1つを回答します。
この方法でsmall-1は通りました。small-2はテーブルを作り終わる前にタイムアウトでした。
ちなみにRubyだと、Array#repeated_combination, Array#combination, Array#injectで一瞬でテーブルが作れました。超便利。
