Codeforces #562 Div1 A. Increasing by Modulo

この回はまぁまぁいい出来だったようだ。
https://codeforces.com/contest/1168/problem/A

問題

N要素の整数列が与えられる。
各値は0～(M-1)の値を取る。

数列のうち任意の個数を選択し、一気にそれらをインクリメントする(ただしMに到達した要素は0に戻す)という処理を繰り返し、数列を単調増加にすることを考える。
最少何回処理を行えばよいか。

解法

二分探索で解く。
処理回数が定まった場合、数列の後ろから取りえる値のうち最大を保つように値を設定したとき、単調増加にできるか判定すればよい。

int N,M;
int A[303030];

int ok(int v) {
	int pre=M-1;
	int i;
	if(v<0) return 0;
	for(i=N-1;i>=0;i--) {
		if(pre>=A[i]) {
			pre=min(pre,A[i]+v);
		}
		else {
			if(A[i]+v<M) return 0;
			pre=min(pre,(A[i]+v)%M);
		}
	}
	return 1;
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,N) cin>>A[i];
	
	int ma=M-1;
	for(i=19;i>=0;i--) if(ok(ma-(1<<i))) ma-=1<<i;
	cout<<ma<<endl;
}
||

*まとめ