Mice's Luck(ネズミ達の運) [yukicoder No.667]

https://yukicoder.me/problems/no/667

解法

https://yukicoder.me/submissions/246520

i匹目についてはSの[i,N-1]の範囲において、「(oの個数)/(残りの個数)*100」を計算して出す。
分母の(残りの個数)はN-iであるため、分子を高速に計算する必要がある。
これは「ok := 残っているoの数」を順次更新していくことでO(1)が達成できる。

string S;
int N;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> S;
    N = S.length();

    int ok = 0;
    fore(c, S) if (c == 'o') ok++;

    rep(i, 0, N) {
        double ans = 1.0 * ok / (N - i) * 100;
        printf("%.10f\n", ans);
        if (S[i] == 'o') ok--;
    }
}