ARC 039 B 直線塗り

2015/06/20 (Sat) ARC AtCoder アドホック

問題

日本語

方針

後ろから見ていって,塗られていないところを見つけたら そこから $R$ 歩下がったところに塗り始めのフラグを立てる. この処理が終わったら,前から見ていって,フラグを立てたとろから塗るということを,全体が塗られるまで繰り返す.

実装

signed main(){
    memset(dp,-1,sizeof dp);
    int N,R;
    string s;
    cin >> N >> R >> s;
    string S = s;
    int k = N-1;
    vector<bool> flg(N);
    while(k >= 0){
        if(s[k] == '.'){
            for(int i = k; i > max(0,k-R); i--){
                s[i] = 'o';
            }
            flg[max(0,k-R+1)] = true;
            k = k-R;
        } else {
            k--;
        }
    }
    int ans = 0, pos = 0;
    while(pos < N){
        {
            bool end = true;
            rep(i,N) if(S[i] == '.') end = false;
            if(end) break;
        }
        if(flg[pos]){
            ans+=2;
            for(int i=pos;i<min(N,pos+R);i++) S[i] = 'o';
            dump(pos,2);
            {
                bool end = true;
                rep(i,N) if(S[i] == '.') end = false;
                if(end) ans--;
            }
        } else {
            ans+=1;
            dump(pos,1);
        }
        pos++;
    }
    dump(flg);
    cout << ans << endl;
}