AtCoder AGC #026 : D - Histogram Coloring

本番、左からとか下からとか色々考えたけど、上からは考えなかった…。
https://beta.atcoder.jp/contests/agc026/tasks/agc026_d

問題

N列正方形のブロックが積まれている。i列目の高さはH[i]である。
これらのブロック群を赤青に塗り分けることを考える。
この時、2*2のブロック領域において、赤・青のブロックが２回ずつ出てくるような塗り分け方は何通りか。

解法

上から順に塗っていくことを考える。
上の行の色が定まっているとき、その次の行の塗り方は以下のいずれかである。

• 上の行の色を赤青反転する。
• 上の行が赤青交互に並んでいる場合、上の行をそのまま複製することができる。

Hが大きいので1行ずつ処理することはできないので、複数行まとめて処理することを考えよう。
元のブロック群を、以下のように長方形領域に分割する。

• 残ったブロックのうち、最下段の長方形の幅が最大となるようにし、その範囲で高さを最大にする。

こうすると、分割した長方形領域が最下段を根とした根付き木になる。
上から順に長方形Rに対し以下の２値を求めていこう。

• dp1(r) := 長方形Rおよびその上に乗る長方形において、各行が赤青交互に並んでいる場合の組み合わせ数。
• dp2(r) := 長方形Rおよびその上に乗る長方形において、題意を満たす塗り分け方の総数

長方形Rの高さをh、幅のうち上に長方形が乗ってない列数をw、上に乗る長方形群をr1,r2...とする。
すると上記値は以下のように計算できる。最後の(2^h-2)は公式Editorialと異なるので気を付けよう。

• dp1(R) = 2^h * prod(dp1(r))
• dp2(R) = 2^w * prod(dp1(r) + dp2(r)) + (2^h-2)*prod(dp1(r))

前者の考え方は容易で、h行について赤青…の順で塗るか青赤…の順で塗るか選べるので2^h通りとなる。
後者は、(上に他の長方形がないため)この長方形で始めて色を任意に決められる列がw個あるので2^wがかかる。
これは全行において前者の毎行反転するパターンを取るケースである。
dp2の積を取るのはわかりやすいが、dp1が加算されるのは上に乗る長方形の最下段の色を、Rの最上段に複製するケースも許容されるのでその分加算される。
後半の項は、h行のうち毎行反転するパターン以外、すなわち１回以上複製するパターンを加算している。
毎行反転するパターンは前半の項ですでに考慮されているので、その分取り除かなかければならない。

int N;
int H[105];
ll mo=1000000007;

ll modpow(ll a, ll n = mo-2) {
	ll r=1;a%=mo;
	while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1;
	return r;
}

pair<ll,ll> hoge(int L,int R,int v) {
	ll dp1=1,dp2=1;
	int i;
	
	if(L>R) return {-1,1};
	
	int mi=1<<30;
	for(i=L;i<=R;i++) mi=min(mi,H[i]);
	int W=R-L+1;
	for(i=L;i<=R;i++) if(mi!=H[i]) W--;
	
	int pre=L-1;
	for(i=L;i<=R;i++) {
		if(mi==H[i]) {
			auto r=hoge(pre+1,i-1,mi);
			if(r.first>=0) {
				(dp1*=r.first)%=mo;
				(dp2*=r.first+r.second)%=mo;
			}
			
			pre=i;
		}
	}
	auto r=hoge(pre+1,R,mi);
	if(r.first>=0) {
		(dp1*=r.first)%=mo;
		(dp2*=r.first+r.second)%=mo;
	}
	
	(dp2=dp2*modpow(2,W)+(modpow(2,mi-v)+mo-2)*dp1)%=mo;
	(dp1*=modpow(2,mi-v))%=mo;
	
	return {dp1,dp2};
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	for(i=1;i<=N;i++) cin>>H[i];
	cout<<hoge(1,N,0).second<<endl;
}

まとめ

Editorialで数字が誤ってるの勘弁してほしい…。