kmjp's blog

競技プログラミング参加記です

AtCoder ABC #161 : E - Yutori

今回の問題はコード量が短め。
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がいるかと思ったら思ったよりシンプルだった。