Codeforces ECR #141 : E. Game of the Year

7問回の割に難しかった回。
https://codeforces.com/contest/1783/problem/E

問題

N体の敵がおり、2人でそれらを倒す。

両者は、互いにK回ずつ敵に攻撃する。
i番の敵には先手はA[i]回目、後手はB[i]回目の攻撃で敵を倒せる。
いずれかが敵を倒したら、お互い次の敵に進む。

先手がすべての敵を倒せるKを列挙せよ。

解法

各敵に対し、先手が先に敵を倒せるKの区間を考える。
A[i]・B[i]は高々Nなので、K=1～√Nはそれぞれ総当たりしよう。
Kが√N以上の場合、先手が何ターン目の攻撃で敵を倒すか総当たりすれば、合わせて敵1体あたりO(√N)で判定できる。

int T,N,A[202020],B[202020];
int ok[202020];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N;
		FOR(i,N+2) ok[i]=0;
		FOR(i,N) cin>>A[i];
		FOR(i,N) cin>>B[i];
		FOR(i,N) {
			if(A[i]<=B[i]) {
				ok[1]++;
				ok[N+1]--;
			}
			else {
				for(j=1;j<=min(N,455);j++) {
					if((A[i]+j-1)/j==(B[i]+j-1)/j) {
						ok[j]++;
						ok[j+1]--;
					}
				}
				for(j=0;j<=455;j++) {
					int R=(j==0?1<<20:(B[i]-1)/j);
					int L=(A[i]+j)/(j+1);
					L=max({L,456});
					R=min({R,N});
					if(L<=R) {
						ok[L]++;
						ok[R+1]--;
					}
				}
			}
		}
		vector<int> V;
		for(i=1;i<=N;i++) {
			ok[i]+=ok[i-1];
			if(ok[i]==N) V.push_back(i);
		}
		cout<<V.size()<<endl;
		FORR(v,V) cout<<v<<" ";
		cout<<endl;
		
	}
}

まとめ

なんか妙な問題設定。