Codeforces ECR #168 : E. Level Up

Hackされたの残念。
https://codeforces.com/contest/1997/problem/E

問題

N体のモンスターがおり、それぞれの強さはA[i]である。

プレイヤーの初期の強さは1であり、パラメータKがあったとする。
プレイヤーは先頭のモンスターと順に対面し、以下の行動をとる。

• プレイヤーの強さがモンスターの強さより高いとき、モンスターは逃げ戦わない。
• プレイヤーの強さがモンスターの強さ以下の時、プレイヤーとモンスターは戦う。プレイヤーはモンスターとK体戦うたびに強さが1増す。

この条件のもと、以下のクエリに答えよ。

• パラメータKが指定されたとき、m体目のモンスターとは戦うかどうか

解法

Kの大小で分ける。境界値をBとして

• KがB以上の場合
  • プレイヤーの強さはN/K+1以下である。
  • そこで、事前にdp(n,k) := n体目までのモンスターのうち、強さがk以上のモンスターの数
  • dp(n,k)を二分探索すれば、プレイヤーが今の強さで戦うK体目のモンスターの番号がわかる。これをO(N/K)回繰り返し、途中m体目のモンスターと対面したときの強さを求める
• KがB未満の場合
  • 各Kについて、実際にシミュレーションする。

int N,Q;

int A[202020];
const int DI=2000;

int win[121+1][202020];
int ret[202020];
int num[202020];
int X[202020],Y[202020];
vector<int> ev[DI+1];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>Q;
	FOR(i,N) cin>>A[i];
	
	for(x=1;x<=121-2;x++) {
		FOR(i,N) {
			win[x][i+1]=win[x][i];
			if(A[i]>=x) win[x][i+1]++;
		}
	}
	
	FOR(i,Q) {
		cin>>x>>y;
		if(y>=2000) {
			int cur=0;
			int lv=1;
			int ok=0;
			while(cur<N) {
				int nex=lower_bound(win[lv]+min(N+1,cur+y-1),win[lv]+N+1,win[lv][cur]+y)-win[lv];
				if(x<=nex) {
					if(A[x-1]>=lv) ret[i]=1;
					break;
				}
				cur=nex;
				lv++;
			}
		}
		else {
			ev[y].push_back(i);
			X[i]=x;
		}
	}
	
	for(x=1;x<=2000+2;x++) {
		int step=x;
		FOR(i,N) {
			num[i]=0;
			if(A[i]>=step/x) {
				num[i]=1;
				step++;
			}
		}
		FORR(e,ev[x]) ret[e]=num[X[e]-1];
	}
	
	
	FOR(i,Q) {
		if(ret[i]) cout<<"YES"<<endl;
		else cout<<"NO"<<endl;
	}
}

まとめ

なんかこういう場合分けはCodeforcesの印象があるな。