Codeforces #1022 : Div2 F. Fallen Towers

コードは短い。
https://codeforces.com/contest/2108/problem/F

問題

N要素の整数列Aが与えられる。
N個のタワーが並んでおり、i個目のタワーの高さはブロックA[i]個分である。

ここで、タワーiを倒すと以下が発生する。

• 右側にあるA[i]個分のタワーの高さが1ずつ増える。ただし、N個からはみ出た分のブロックは消滅ずる。
• その後、A[i]=0となる。

N個のタワーを任意の順で1回ずつ倒すものとする。
最終的なAを昇順になるようにせよ、その際、mex値を最大化せよ。

解法

ある倒しかたで得られた数列Aがあるとき、各要素B[i]≦A[i]を満たす任意のBが構築できる。
よってmex値がxとなるようにできるなら、x-1となるようにもできる。
そのため、解xは二分探索可能となる。
B=[0,0,0,...,0,1,2,3...,x-1]を構成できればmex値がxになるので、そのような倒し方が可能か判定しよう。

int T,N,A[101010];
int add[101010];

int ok(int v) {
	int i;
	FOR(i,N) add[i]=0;
	FOR(i,N) {
		int tar=max(0,v-1-(N-1-i));
		if(i) add[i]+=add[i-1];
		if(add[i]<tar) return 0;
		int more=A[i]+add[i]-tar;
		add[i+1]++;
		add[min(N,i+more+1)]--;
	}
	return 1;
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N;
		FOR(i,N) cin>>A[i];
		int ret=0;
		for(i=20;i>=0;i--) if(ok(ret+(1<<i))) ret+=1<<i;
		cout<<ret<<endl;
		
	}
}

まとめ

回答が短くて済むせいか、upsolve数が多い気がする。