CodeFestival2014 H問題 部屋割り

発想が思いついたのは良かった。ただ、実装が…

この問題って、単純に前から走査して最終的な部屋割り、また、各々が部屋に入るとき、何人部屋に入るかを知ることができる。
そうしたら最終的な部屋割りから最初の方に向かっていって走査していく。
そのときに、あとから期待値として何人上に入ってくるかを計算していけばよい。

kmjpさんの実装が素晴らしかった…。
自分の良くない癖でmapで部屋割りを作っていったんだが、it = mp.begin()とかしてmp[it->first+1]を触ったりするとitの位置が変化したりとかして本当に大変だった。
こういう連続して並び、かつ最初と最後しか触らないんだったら、配列とmin, maxの変数だけで構成すればいいというのは勉強になった。

const int MAXN = 200005;
int mp[MAXN];
int mi, ma;
int rn[MAXN];
double ans[MAXN];
double np[MAXN];

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);

    int N, K;
    cin >> N >> K;
    string S;
    cin >> S;

    mp[0] = K;
    rep(i, N){
        if(S[i] == '0'){
            rn[i] = mi;
            mp[mi]--;
            mp[mi+1]++;
            ma = max(ma, mi+1);
            if(mp[mi] == 0) mi++;
        }else{
            rn[i] = ma;
            mp[ma]--;
            mp[ma+1]++;
            while(mp[mi] == 0) mi++;
            ma++;
        }
    }

    for(int i=N-1; i>=0; i--){
        int n = rn[i];
        ans[i] = n+1+np[n+1];
        np[n] = (np[n]*mp[n] + (np[n+1]+1.0)*1.0)/(mp[n]+1.0);
        mp[n+1]--;
        mp[n]++;
    }

    rep(i, N){
        printf("%14.14lf\n", ans[i]);
    }
}