読者です 読者をやめる 読者になる 読者になる

Google Code Jam Qualification Round - D問題「GoroSort」

Dashboard - Qualification Round 2011 - Google Code Jam

※ かなり変な日本語訳をしていますので、その点ご了承ください。

問題

Goroには4本の腕があり、とても強い。君は彼と関わり合いにならない方がいいね。
GoroはN個の互いに異なる整数をソートしたがっている。
でも"アルゴリズム"なんてものはGoroの得意分野ではないのさ。
彼が強いのは腕っぷしだけ、ってこと。

そこでGoroはピンと閃いたんだ。
彼の2本の腕を使っていくつかの整数を押さえ、
残りの2本の腕でもって机をバン!と強く叩く方法をね。
押さえていない整数は空中にフワッと飛んで、
ランダムにシャッフルされてまた机に戻ってくる、って寸法さ。

Goroはなるべく速くソートしたいんだ。
与えられた整数列をソートするために、彼は平均で何回机を叩けばいいのだろうね?
もちろん彼はなるべく頭を使って、どの整数を机に押さえつけるかは最適なものを選ぶものとするよ。
Goroの指は無数にあるから、机の上の整数は何個でも押さえられる。

もう少し正確に言おうか。
机の上にある整数の任意の部分集合を、
Goroは机を叩く前に選んで机に固定させることができるのさ。
そして彼は机を叩く直前の様子を見て、
どの整数を固定させるかを毎回選択しなおすことも出来るのさ。

机を叩いたときにシャッフルされる整数は、
完全にランダムにシャッフルされるものとして考えてね。
(取り得る全ての状態が同じ確率で現れるってこと!)

入力

最初の1行にテストケース数Tがあり、T個のテストケースが後に続く。
各テストケースは2行から成り、
1行目にはNが入力され、
2行目はGoroがソートすべき整数がその順番通りに入力される。

出力

各テストケースごとに"Case #x: y"を出力する。
xはテストケース番号(1から始まる)で、
yはGoroが最適な戦略で机を叩いた場合の机を叩く回数の期待値。
答えは誤差「10の-6乗」まで許容する。

制限

1 ≦ T ≦ 100;

各テストケースのN個の整数は、N以下の正整数の順列のいずれか。

Small dataset

1 ≦ N ≦ 10;

Large dataset

1 ≦ N ≦ 1000;

サンプル

Input 

3
2
2 1
3
1 3 2
4
2 1 4 3
 	
Output 
 
Case #1: 2.000000
Case #2: 2.000000
Case #3: 4.000000

補足説明

上記のテストケース#3について、1つの戦略として下記のようなものがある。
まず左の2つの整数を固定して机を叩く。
すると3と4が空中に舞う。
机に着地したとき、3と4は正しい順序の [3, 4] に1/2の確率でなり、
間違った順序の [4, 3] にも1/2の確率でなる。
つまり、平均で2回叩けば正しい順序になる。
続けてGoroは3と4を固定して、1と2が正しい順序になるまで机を叩く(平均で2回)。
このとき、総合して机を叩く回数の期待値は 2 + 2 = 4回 となる。

所感
この問題には見事にやられました。大学の頃に学んだ線形代数やら順列やらを復習しながら、ほぼ紙とペンで解いた感じです。答えがわかった瞬間の気持ち良さを久々に味わったような気がします(頭がボケてただけかも)。まさかこんなページまで見ることになろうとは思いませんでしたが。ちなみに、プログラムとしては今回のQualification Roundの中で最も行数が少なくなりました。


プログラミングコンテストチャレンジブック

プログラミングコンテストチャレンジブック

プログラマのための論理パズル 難題を突破する論理思考トレーニング

プログラマのための論理パズル 難題を突破する論理思考トレーニング