Codeforces #771 : Div2 F. Two Posters

Fだけ極端に難しかった回。
https://codeforces.com/contest/1638/problem/F

問題

幅Nの壁がある。
この壁は1*1のタイルを敷き詰めたもので、横棒に対し、i列目にはH[i]個のタイルが縦にぶら下がったような形状になっている。
各列、下から上にタイルを押し込むことで、各列いくつか棒の上にタイルを出すことができる。

ここに、2つの矩形を占めるポスターを貼りたい。
ポスターのある位置は全面タイルがなければならず、ポスターが重なってはならない。
2枚のポスターの面積の和の最大値を求めよ。

解法

• 2枚のポスターが列を共有しない場合は容易。ポスター1枚置く場合についてはO(N^2)掛ければ、ある列の範囲内の最大値を列挙できるので、そこから容易に計算可能。
• 1枚目の列の範囲が、2枚目の範囲を包含する場合
  • 共通する列のうち、全タイルを使う列を1つ定めて総当たりする。1枚目の列を尺取り法の要領で左右に伸ばしていくことを考える。2枚目の高さはその時点で確定するので、やはり尺取り法の要領で2枚目の左右をどこまで伸ばせるか総当たりする。
• 2枚がともに一部の列を共有する場合
  • こちらも共通する列を総当たりする。1枚目の左端を左に伸ばしていきその範囲で極力高さを高くすることを考える。
  • 同じく尺取り法の要領で、2枚目の右端の最適値を更新していく。

int N;
ll H[1010101];
ll mi[10101];
ll ma;
ll L[10101];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>H[i+1];
	
	// separate
	for(i=0;i<=N;i++) {
		ll a=H[i];
		L[i]=a;
		for(j=i-1;j>=0;j--) {
			a=min(a,H[j]);
			L[i]=max(L[i],a*(i+1-j));
		}
		
		ll r=H[i];
		a=H[i];
		for(j=i+1;j<=N+1;j++) {
			a=min(a,H[j]);
			r=max(r,a*(j-i+1));
		}
		FOR(j,i) ma=max(ma,r+L[j]);
	}
	
	for(i=1;i<=N;i++) {
		int TL=i,TR=i;
		while(H[TL-1]>=H[i]) TL--;
		while(H[TR+1]>=H[i]) TR++;
		ma=max(ma,H[i]*(TR-TL+1));
		mi[i]=H[i];
		for(j=i+1;j<=N+1;j++) mi[j]=min(mi[j-1],H[j]);
		for(j=i-1;j>=0;j--) mi[j]=min(mi[j+1],H[j]);

		// accumulated
		ll a=H[i];
		for(int L=i,R=i;L>=1;L--) {
			a=min(a,H[L]);
			while(H[R+1]>=a) R++;
			ma=max(ma,a*(R-L+1)+(H[i]-a)*(TR-TL+1));
		}
		a=H[i];
		for(int L=i,R=i;R<=N+1;R++) {
			a=min(a,H[R]);
			while(H[L-1]>=a) L--;
			ma=max(ma,a*(R-L+1)+(H[i]-a)*(TR-TL+1));
		}
		// cross
		a=H[i];
		ll rma=0;
		for(int L=i,R=N+1;L>=1;L--) {
			a=min(a,H[L]);
			ll dif=H[i]-a;
			while(R>TR&&mi[R]<dif) {
				rma=max(rma,mi[R]*(R-TL+1));
				R--;
			}
			rma=max(rma,dif*(R-TL+1));
			ma=max(ma,a*(TR-L+1)+rma);
		}
		a=H[i];
		rma=0;
		for(int L=0,R=i;R<=N;R++) {
			a=min(a,H[R]);
			ll dif=H[i]-a;
			while(L<TL&&mi[L]<dif) {
				rma=max(rma,mi[L]*(TR-L+1));
				L++;
			}
			rma=max(rma,dif*(TR-L+1));
			ma=max(ma,rma+a*(R-TL+1));
		}
	}
	
	
	
	cout<<ma<<endl;
	
}

まとめ

こういうの単時間で詰めていくのしんどいな。