ARC 039 B 直線塗り
問題
方針
後ろから見ていって,塗られていないところを見つけたら そこから $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;
}