WARush

SRMの結果とか、解けた問題のコードを書いていきます

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;
    }
};