今回の問題はコード量が短め。
https://atcoder.jp/contests/abc161/tasks/abc161_e
問題
N日間でK日働きたい。
パラメータとして、N日中働けない日の一覧が与えられる。
また、1日働くと以後C日間働けない。
N日中、「この日を逃すとK日働けない」という日を列挙せよ。
解法
事前準備として、できるだけ早く働くとき、i回目に働く日を求める。
同様に、K回働ける範囲で、それぞれi回目に働く最も遅くてよい日を求める。
各i日目に対して、以下を判定しよう。
i日目以前に最大a回働け、その日をj日目とする。max(i+1,j+C+1)日目以降であとK-a回働けるかを判定する。
int N,K,C; string S; int A[202020]; vector<int> L,R; void solve() { int i,j,k,l,r,x,y; string s; cin>>N>>K>>C>>S; C++; L.push_back(-1<<20); FOR(i,N) if(S[i]=='o') { if(L.back()+C<=i) L.push_back(i); } R.push_back(-1<<20); for(i=N-1;i>=0;i--) if(S[i]=='o') { if(i+C<=-R.back()) R.push_back(-i); } FORR(r,R) r=-r; reverse(ALL(R)); FOR(i,N) if(S[i]=='o') { x=lower_bound(ALL(L),i)-L.begin()-1; y=L[x]; j=lower_bound(ALL(R),max(y+C,i+1))-R.begin(); j=R.size()-1-j; if(x+j<K) cout<<i+1<<endl; } }
まとめ
複雑なDPやSegTreeがいるかと思ったら思ったよりシンプルだった。