TopCoder SRM 647 Div1 Easy BuildingTowersEasy、Div2 Hard BuildingTowers

Div1 Easyの難しい版がDiv2 Hardで出るという珍しいスタイル。
http://community.topcoder.com/stat?c=problem_statement&pm=13634
http://community.topcoder.com/stat?c=problem_statement&pm=13606

問題

1～N番の建物を一列に立てたい。
その時、以下の条件を満たしたい。

• 1番の建物の高さは0である。
• 隣接する建物の高さの差はK以内である。
• 幾つかの建物においては、x[i]番の建物が高さt[i]以下でないといけないという条件が与えられる。

条件を満たした中で立てられる最大の建物の高さを答えよ。

解法

最初の条件が面倒なので、x[0]=1、t[0]=0としてx,tの先頭に入れてしまおう。

Div1 EasyはNが10^5以下なうえKが1固定なので、まずこちらを考える。

全部の建物の高さの初期値をH[i]=Nとする。
ただし、x[i]番の建物はH[x[i]]=t[i]とする。
隣接する建物の高さは１以内でないといけないので、H[i]=min(H[i],H[i-1]+1,H[i+1]+1)をiを増やす方向と減らす方向に２回総当たりしてやればよい。

Div2 HardはKが可変なうえ、Nの最大値が10^9なので全部の建物の高さをH[i]に持つことはできない。
ただ、上で考えたH[i]の式は応用できる。すなわちx[i]に対応するH[x[i]]だけを考えて、
H[x[i]]=min(H[x[i]], H[x[i-1]]+K*(x[i]-x[i-1]), H[x[i+1]]+K*(x[i+1]-x[i]))を同様にiを増加・減少方向に２回ループすればよい。

次に、H[x[i]]とH[x[i+1]]の関係からx[i]～x[i+1]の間に出来るだけ高い建物を作ることを考える。
既に|H[x[i]]-H[x[i+1]]| == K*(x[i+1]-x[i]) だったらH[x[i]]かH[x[i+1]]が最高位。

それ以外、|H[x[i]]-H[x[i+1]]| ＜ K*(x[i+1]-x[i])の場合を考える。
L=min(H[x[i]],H[x[i+1]])、 R=max(H[x[i]],H[x[i+1]])、D=x[i+1]-x[i]とする。
すなわち、高さLとRの建物を建物D個分の距離で配置するとき、最高位を高くすることを考える。

まず両者の差がK未満となるよう、L+=(R-L)/K*K、D-=(R-L)/Kで更新しておく。
この時：

• Dが偶数なら、SからD/2個分K上昇した建物を建てられるので最高位はS+D/2/K。
• Dが奇数なら、LからD/2個分K上昇した建物を建てられるので最高位はL+D/2/K。

上記処理を各iに対して行い、最高位を求めればよい。

class BuildingTowers {
	public:
	long long maxHeight(int N, int K, vector <int> x, vector <int> t) {
		vector <ll> X,T;
		int i,j,k;
		N--;
		X.push_back(0);
		T.push_back(0);
		FOR(i,x.size()) if(x[i]!=1) X.push_back(x[i]-1),T.push_back(t[i]);
		if(X.back()!=N) X.push_back(N),T.push_back(1LL<<60);
		
		int M=X.size();
		FOR(i,M) {
			FOR(j,M-1) {
				T[j]=min(T[j+1]+(X[j+1]-X[j])*K,T[j]);
				T[j+1]=min(T[j]+(X[j+1]-X[j])*K,T[j+1]);
			}
		}
		
		ll ma=0;
		FOR(i,M) ma=max(ma,T[i]);
		FOR(i,M-1) if((X[i+1]-X[i])*K>T[i+1]-T[i]) {
			ll s=min(T[i+1],T[i]),l=max(T[i+1],T[i]);
			ll d=X[i+1]-X[i];
			d-=(l-s)/K;
			s+=(l-s)/K*K;
			if(d%2) ma=max(ma,l+(d/2)*K);
			else ma=max(ma,s+(d/2)*K);
		}
		return ma;
		
	}
}

まとめ

Div2 HardはDの偶奇で微妙に結果が異なることに気づかず、1WA。
よい難易度の上げ方だった。