Codeforces Global Round 10 : F. Omkar and Landslide

解ける問題は解き切ってなんとかレート増。
https://codeforces.com/contest/1392/problem/F

問題

元々真に単調増加である整数列Hが与えられる。
H[i]とH[i+1]に2以上差があるとき、H[i]をインクリメントし、H[i+1]がデクリメントする、という処理が可能な限り行われたとき、Hは最終的にどうなるか。

解法

Hが単調増加であることが保たれている場合、H[i]とH[i+1]の間で処理が行われると、H[i-1]とH[i]の差が2以上になるので次はそこで処理が行われる。

そうすると、最終的にHは、隣接要素は基本的に1だけ差がある。ただし1か所だけ差が0になってもよい、という形になる。
あとは二分探索などの形でH[0]の値を仮置きすると、上記差が0になる箇所も計算で求められる。
よってO(N+log(sum(H)))で解くことができる。

int N;
ll H[1010101],T[1010101];
int vis[1010101];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	scanf("%d",&N);
	ll S=0;
	FOR(i,N) {
		scanf("%lld",&H[i]);
		S+=H[i];
	}
	
	ll V=0;
	ll lef=S;
	for(i=40;i>=0;i--) {
		ll A=V+(1LL<<i);
		ll sum=(A+A+(N-1))*N/2;
		if(sum<=S) V=A, lef=S-sum;
	}
	
	FOR(i,N) {
		T[i]+=V+i;
		if(i<lef) T[i]++;
	}
	
	
	FOR(i,N) _P("%lld ",T[i]);
	
	_P("\n");
	
}

まとめ

最初から昇順というのがミソだね。