TCO15 Round 2B easy:Bitwisdom

TCO Round2Bに参加。結果はeasyだけ解いてレーティングが元通りくらいに復帰しました。

しばらくSRMはなさそうなのでSRMの練習は練習会だけにしてこどふぉの練習しようかなと思います(div1 のABC)。
med解けないとSRMのレートも高くて1800くらいで止まりそうなのでなんとかしたいですが…

問題

TopCoder Statistics - Problem Statement

解法

DPが正統派な気がしてきましたが本番は貪欲(?)っぽい方法で解きました。

ビットを反転させる回数は,基本的には0と1が隣り合って並んでいる回数と同じになります。
例えば010だと2回,110だと1回,100011だと2回などなど。
ただ,すべての数字が1の場合は例外で,この場合は1回になります。

0と1が隣り合って並んでいる回数の期待値は期待値の線形性を使えば簡単に求めることが出来ます。

これで良い理由はそれほど考えてませんが0と1が隣り合ったら1回反転させざるを得ないと考えれば当たり前な気がします(は？当たり前じゃねぇよとかあったら教えて欲しいです)。

class Bitwisdom {
public:
    double expectedActions(vector <int> P) {
        int n = P.size();
        vector<double> p(n);
        for (int i = 0; i < n; i++) {
            p[i] = 1.*P[i]/100;
        }
        double ans = 0;
        {
            double tmp = 1;
            for (int i = 0; i < n; i++) tmp *= p[i];
            ans += tmp;
        }
        for (int i = 0; i < n-1; i++) {
            ans += (1-p[i])*p[i+1] + p[i]*(1-p[i+1]);
        }
        return ans;
    }
};