CodeForces #562 Div2 C. Increasing by Modulo

Problem - C - Codeforces

概要

0以上m未満の整数からなるn項の数列aが与えられる。
各項にmod mで最大x回1を足すことで、aを非減少数列にすることできるとき、最小のxを答えよ。

制約

1 ≦ n, m ≦ 300 000

方針

すでに問題を言い換えている。

xを決めうつことで2分探索が使える。xが与えられたとき、aを非減少数列にする方法は次の通り。
・最初の項はa0+xがm以上となるなら0とし、そうでないならa0のまま。
・現在の項をaiとし、前の項をbとする。
　ai=bのとき、そのまま。
　ai<bのとき、ai+x≧bならai=bとできるが、そうでないならaを非減少にすることはできない。
　ai>bのとき、ai+x = b (mod m)とすることができればai=bとする。そうでなければaiのまま。

解答

Submission #54818427 - Codeforces

#include <bits/stdc++.h>
#define rep(i,n) for(int i=(0);i<(n);i++)

using namespace std;

typedef long long ll;

int n, m;
vector<int> a;

bool cond(int x){
	int bef = a[0] + x >= m ? 0 : a[0];
	for(int i = 1;i < n; i++){
		if(a[i] == bef) continue;

		if(a[i] < bef){
			if(bef - a[i] > x) return false;
			continue;
		}

		int t = a[i] + x;
		if(t < m) {
			bef = a[i];
		}else{
			t %= m;
			if(t < bef) bef = a[i];
		}

		// cout << i << "," << a[i] << "," << bef << endl;
	}

	return true;
}

// condを満たす最小のxを求める(lower_bound)
// 全てのxが条件を満たさない場合はnを返す(nはとりえない値)
int lower_bound_cond(){
	int lb = -1, ub = m;

	while(ub - lb > 1){
		int mid = (lb + ub) / 2;

		bool ok = cond(mid);
		// cout << mid << "," << ok << endl;
		if(ok) ub = mid;   // Answer is in (lb, mid]
		else lb = mid;            // Answer is in (mid, ub]
	}

	// now lb + 1 = ub
	return ub;
}

int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);

	cin >> n >> m;

	a.resize(n);
	rep(i, n) cin >> a[i];

	cout << lower_bound_cond() << endl;

}