Codeforces #300 Div1 C. Tourist's Notes

CF#300に参加。
Div1/2合同会だったため、12Hackしたけど解いた問題数が少なく微妙な順位でレート減。
http://codeforces.com/contest/538/problem/C

問題

N個の連なる山があり、そのうちM個D[i]の高さH[D[i]]が与えられる。

隣接する山同士の高さの差は1以下でなければならない。
条件を満たす山の配置は存在するか。また、存在するなら最大の山の高さはどの位か。

解法

まず、D[i]とD[i+1]について、|H[D[i]]-H[D[i+1]]|≦|D[i]-D[i+1]|出なければ条件を満たさない。
条件を満たす場合、D[i]とD[i+1]の間の最高点はmax(H[D[i]],H[D[i+1]])+|D[i]-D[i+1]|/2となる。

なお、H[0]とH[N-1]が最高になるケースは別途処理する必要がある。

int N,M;
int D[101000],H[101000];
int ma=0;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,M) cin>>D[i]>>H[i];
	ma=max(ma,H[0]+(D[0]-1));
	ma=max(ma,H[M-1]+(N-D[M-1]));
	FOR(i,M-1) {
		if(abs(H[i+1]-H[i]) > D[i+1]-D[i]) return _P("IMPOSSIBLE\n");
		int d=D[i+1]-D[i];
		int lo=min(H[i+1],H[i]);
		int hi=max(H[i+1],H[i]);
		d-=hi-lo;
		ma=max(ma,hi+d/2);
	}
	cout<<ma<<endl;
}

まとめ

最近max(H[D[i]],H[D[i+1]])+|D[i]-D[i+1]|/2 この式使う問題よく見るな…。