Problem D. GoroSort
hoyohoyoさんから日本語訳教えてもらった。
結局わかりませんでした。
問題概要
ゴローは、4本の腕があります。
ゴローは、N個の異なる要素を持つ整数をソートする必要があります。
ゴローの計画は、２本の腕で配列のいくつかの要素を抑えつけて、
残りの腕（３本目と４本目）で机を攻撃します。
攻撃すると、抑えられていない要素はランダムに動きます。
ゴローが最適戦略をとるとき、ソートを完了するには何回机を攻撃する必要がありますか？
期待値を答えてください。
試行錯誤のめも
※注意：馬鹿の試行錯誤なので参考にはなりえません
期待値わかんねー、完全に投げぎみw
たぶんDPで最適解求めたらよさそうな雰囲気、問題は式が立てられないこと。
1*0.5 + 2*0.25 + 3*0.125 .... = 2 に収束するらしい
とりあえず書き出す。
求めたい期待値の確率変数は ソートするまでにテーブルを叩いた回数
要素が2つなら、合うか合わないかの2択だけど、
要素が3つのとき、
123:3
132:1
213:1
231:0
312:0
321:1
要素が3つなら、合ってる個数が2個になるわけないよねw
たぶん期待値の線形性を利用して、
要素n個のうち、k個が正しくソートされるために叩く回数の期待値 を求める式が必要？
要素n個のうち1個が正しくソートされる確率は 1/n でいいのかな？
要素n個のうち2個が正しくソートされる確率は 1/n * 1/(n-1) か？
k個は任意でいいはずだから、n_C_k種類あるはずなので、
要素n個のうちk個が正しくソートされる確率は n_C_k / n! かな？
え、これ大丈夫か？…ぜんぜん大丈夫じゃない。配列1000個まであるんだぞ…
というか式間違ってる
馬鹿だから具体例から確かめていかないとだめだ。
要素3個のうち1個が正しくソートされる確率は上記から 1/2 にならないといけない
n_C_k / n_P_k = 3/6 = 1/2
公式を展開すると、 1/k! と等しい、よさそうかな？
よくない、いずれも正しい位置にならない場合がおかしくなる。うーん、確率＞＜
おかしい、プログラミングの問題に取り組んでいるはずなんだが…
例えば、要素が4個なら全部で24パターン
0:9, 1:8, 2:6, 3:0, 4:1
正しい位置が0個 9パターン
正しい位置が1個 8パターン
正しい位置が2個 6パターン
正しい位置が3個 0パターン
正しい位置が4個 1パターン
あー、プレゼント問題？というか、モンモール問題っていうやつかな
漸化式：f(n)=(n-1){f(n-2)+f(n-1)}
要素n個のうちk個が正しくソートされるパターン数は n_C_k * f(n-k) の予感
f(1) = 0
f(2) = 1
f(3) = 2
f(4) = 9
よって、
要素4個のうち0個のパターンが 4_C_0 * f(4) = 9
要素4個のうち1個のパターンが 4_C_1 * f(3) = 8
要素4個のうち2個のパターンが 4_C_2 * f(2) = 6
要素4個のうち3個のパターンが 4_C_3 * f(1) = 0
f(0)=1と定義したほうが楽かも
これで、1回叩いたときに、要素n個のうちk個が正しくソートされる確率 を求めることができる
n_C_k * f(n-k) / n! かな？
うーん、この方向でいいのかなぁ、怪しいというかlargeは無理w
要素n個のうちk個が正しくソートされるためにテーブルを叩く回数の期待値を求めるためには、
要素n個のうちk個が正しくソートされる確率を p とすると、はずれる確率が 1-p = q
1回でソートする確率＋2回でソートする確率＋... の和だから、
1*p + 2*q*p + 3*q^2*p + ...
Σ_{m=1,∞}m*q^(m-1)*p になる。無限級数だから、あー、やめる。
要素n個のうちk個が正しくソートされ"ない"確率を p として、正しくソートされる確率を 1-p とする
Σ_{m=1,∞}m*p^(m-1)*(1-p) = Σ_{m=1,∞}m*(p^(m-1)-p^m) になる。展開すると、
p^0-p^1 + 2*p^1-2*p^2 + 3*p^2-3*p^3 + ...
= p^0 + p^1 + p^2 + p^3 + .... になるような？等比数列の和？
(1-p^∞)/(1-p) になる？ え、∞ですけど…あー、0
いやまて、忘れてるw
= p^0 + p^1 + p^3 + ... - ∞p^∞ これを忘れてた。だから、
(1-p^∞)/(1-p) - ∞p^∞ こんな感じ？ 前者はさっきと同じだから、
1/(1-p) - ∞p^∞ になる、え？あー、0
ちがーうちがーうw
えーっと、初期値（まだソートされてない要素の数）、シャッフルする要素の数、正しくソートされた要素の数
の3つの値が必要だから、2重ループじゃだめなんだ。3重ループだ
あれ。おうふwwwwwwwここに来て大間違いに気付く。
3 1 2 とかなら、どう2個選択しても2個とも正しい位置にはいかない
ということは、配列の要素の位置にも依存するのか…
メモ化再帰で適当に廻して最小値を求める方向に切り替えよう
配列の要素に依存とか、ますますlargeが遠くなった気がするw
えーっと、任意の要素を選択だから、ビット処理でいいかな
だめくさいw、ちょっと考え直そう。
二つの要素ずつ考えていくのが一番いい？サイクルを持つイメージ？
二つの要素を交換して互いに正しいソート位置になるためには、値が相互作用していなければならない
だめだだめだ。全然だめだw
うーん、色々奔走してみたものの、やっぱり確率・期待値はわからないという結論に至る。
わかる人から見ればなにやってんだこいつって感じなんだろうけどw
まず、 3 1 2 の配列の場合の期待値がわからないぞー
