SRM575 Div1 Medium "TheSwapsDivOne"
問題
http://community.topcoder.com/stat?c=problem_statement&pm=12498
訳
Johnは数字のシーケンスを持っていた。
彼とBrusはそのシーケンスで遊ぼうとしている。
まず始めに、Johnが次のような動作をk回繰り返す。
シーケンスのインデックスを2つ選び、そこにある2つの数字を入れ替える。
(Johnはインデックスを一様にランダムに選ぶ。つまり、各動作において、
2つのインデックスのペアそれぞれは、選ばれる期待値が同じである)
その後、BrusはJohnのシーケンスから空でないサブシーケンスを選ぶ。
彼はその選んだサブシーケンスにある数字を全て足して、その結果を紙にメモをとっていく。
(Bursもまた一様にランダムにサブシーケンスを選ぶ。
つまり、サブシーケンス(要素が連続したもの)の候補それぞれは、選ばれる期待値が同じである)
あなたは数字のシーケンスが文字列のリストで与えられる。
リストの全ての文字列を連結したときの文字列をsとする。
文字列s[i]の0 - 9の文字は、Johnが持っているシーケンスのi番目の数字を表している。
Brusがメモを取るサブシーケンスの合計値の、その期待値を返せ。
制約
2 <= sの文字数 <= 47 * 47
1 <= k <= 10^6
meretさんのソースコード
コメント入れて、あと変数名とか変えたものを載せておきます。
参考までに
double val[10005]; // val[i] index i がサブシーケンスで選ばれる期待値 class TheSwapsDivOne { public: double find(vector <string> seq, int k){ // 1つの文字列にする string s; for( vector<string>::iterator it = seq.begin(); it != seq.end(); it++ ){ s += *it; } int n = s.length(); // 違う位置にあったときに、元の位置に戻る確率 double dif_to_same = 2 / (double) (n * (n - 1)); // 元の位置にあったときに、違う位置へ移動する確率 double same_to_dif = 2 / (double) n; // 元の位置にあったときに、元の位置にとどまる確率 double same_to_same = (n - 2) / (double) n; // 違う位置にあったときに、また違う位置へ移動する確率 double dif_to_dif = (n - 2) / (double) n + 2 * (n - 2) / (double) (n * (n - 1)); // Johnがシャッフルした後で、 // 数字が同じ位置にある確率と、違う位置にある確率を出す。 double p_same = 1; // 同じ位置にある確率 double p_dif = 0; // 違う位置にある確率 for (int i = 1; i <= k; ++i) { double n_same = p_same * same_to_same + p_dif * dif_to_same; double n_dif = p_same * same_to_dif + p_dif * dif_to_dif; p_same = n_same; p_dif = n_dif; } // Brusにサブシーケンスとして選ばれる期待値を各インデックスで出す。 memset( val, 0, sizeof(val) ); for (int i = 0; i < n; ++i) { val[i] = 2 * ((i + 1) * (n - i)) / (double) ((n + 1) * n); } double sum = 0; // その合計 for (int i = 0; i < n; ++i) { sum += val[i]; } // 期待値を計算 double res = 0; for (int i = 0; i < n; ++i) { int d = s[i] - '0'; // index i がサブシーケンスで選ばれる期待値 double val_i = val[i]; // index i以外 がサブシーケンスで選ばれる期待値の平均 double val_non_i = (sum - val[i]) / (n - 1); res += (p_same * val_i + p_dif * val_non_i) * d; } return res; } };