Google Code Jam Qualification Round 2011

GCJ

終わったので、感想など。
とはいってもほとんどDの解説のようななにかですが・・・

ソースはこの辺から http://www.go-hero.net/jam/11/name/YUKI.M

とりあえず、全部通って100ptでした。
わーい、やったねー。
慣れないHaskellでやったせいで、通算10時間くらいかかってますがね・・・。
全体的な感想としては、基本的にやるだけ問題だったのに、Dだけ難易度が異常だと思いました。
Dを一瞬で解いている人たちはどうなってるの、という印象。
そのDもできてしまうと、非常にきれいな解になって、面白い問題だなと思いました。

以下問題ごとの解説とか感想とか。
問題は知ってる前提。

A (Bot Trust)

やるだけ。
１秒ずつシミュレーションしても間に合うらしいです。
私はボタンを押すごとにシミュレーションしました。

B (Magicka)

まどかまぎかは多分関係ない。
英語が難しいけど、理解すればやるだけ。
とくに注意点はないかと。

C (Candy Splitting)

分割できたとすると、

(分割Aのxor) = (あまりのxor)

なので、

(分割Aのxor) xor (あまりのxor) = 0

になります。
つまり全破片のxorをとると0にならない限り、分割できません。

またこのときには、どのような分割をしても、xorしたものは一致するので、弟には一番小さいかけらをあげておきましょうｗ

個人的には一番簡単だった。
あとHaskellでxorするには、Data.Bitsをimportしないといけないらしい。

D (GoroSort)

これはムズイ。

(以下駄文注意)

小さい例で考えてみる。

  • 2 1 4 3 (サンプルインプット。4 3を押さえ、2 1をそろうまでやり、そのあとに1 2を押さえ、4 3をそろうまでやる)
  • 2 3 1 5 4 (5 4を押さえ、2 3 1がそろうまでやり、そのあと1 2 3を押さえ、5 4をそろうまでやる)

つまり、循環している部分に対して独立にやって和をとれば良さそう。
(ここは証明できないので、教えてえらい人)

さて、じゃあ上の2 3 1は何回くらいやればそろうのでしょう。
計算してみましょう。

流れとしては

  • １つもそろわない→もう１回繰り返す
  • １つそろう→そろったやつは押さえて、あとは2つをそろえるのと一緒
  • (２つそろう・・・はありえない。1つだけそろってないってどんな状況だ)
  • ３つそろう

のいずれかであるはずです。

とりあえず

1回のシャッフルでn個中k個がそろう確率：f(n, k)
n個をそろえるのにかかる回数の期待値： A(n)

としましょう。自明にf(n, n) = 1/n! です。
また f(n, k) は確率なので、 n! をかけることで、場合の数になります。

すると、３つ中１つそろう確率f(3,1)は、１つそろう数字を決め、その他の２つはそろわない確率なので
f(3,1) = (3C1 * (f(2, 0) * 2!)) / 3!
となります。
その他については f(3,2) = 0, f(3, 3) = 1 / 3!, f(3, 0) = 1 - f(3, 1) - f(3, 3) で計算できます。

では期待値A(3)はというと、上記のものを全部足せばよいので
A(3) = 1 + (f(3, 0) * A(3) + f(3, 1) * A(2) + f(3, 2) * A(1) + f(3, 3) * 0)
となります。ここからA(3)が計算できます。

さて、では一般にA(n)はどうなるのでしょうか。
まず計算に必要な、f(n,k)を計算しましょう。
f(n, n) = 1 / n! は分かっています。 f(n, 0)は難しいので、f(n, k) (k=1, 2, ..., n-1)を考えましょう。
3の時に考えたのを応用すると
f(n, k) = (nCk * (f(n - k, 0) * (n - k)!)) / n! = f(n - k, 0) / k!
となります。すると
f(n, 0) = 1 - f(n, 1) - f(n, 2) - ･･･ - f(n, n)
で計算できるので、f(n, k)は全て計算できます。

期待値も3のときと同様に考えて
A(n) = 1 + (f(n, 0) * A(n) + f(n, 1) * A(n - 1) + ･･･ + f(n, k) * A(n - k) + ･･･ + f(n, n) * 0)
⇔ (1 - f(n, 0)) * A(n) = 1 + (f(n, 1) * A(n - 1) + ･･･ + f(n, n - 1) * A(1))
⇔ A(n) = { 1 + f(n, 1) * A(n - 1) + ･･･ + f(n, n - 1) * A(1) } / (1 - f(n, 0))
となるのでA(n)も順番に計算していけます。

あとはDPでもメモ化でもなんでもいいので解くだけです。
(ここで昨日のメモ化の話がでてくるんですが・・・)

解いてみると、なんと
A(n) = n
になってるじゃないですか。これはちょっと予想外でした。
ということは、上の計算式はまだ計算できるはずですが、私にはここで限界です。

なにはともあれ、この解法で解いて提出して、無事に通ってました。
ということは最初の仮定はただしかったようで安心しました。
ちなみにA(n) = n になった時点で、位置があってないやつの個数を数えればいいのは気づきましたが、もうコードいじる気力はありませんでしたｗ