kmjp's blog

競技プログラミング参加記です

yukicoder : No.122 傾向と対策 : 門松列（その３）

yukicoder

想定解ではない方法で解いた。
http://yukicoder.me/problems/298

問題

スーパーリッチ門松とは、以下の条件を満たす一列に並んだ7個の門松列である。

  • 1列に並んだ門松の高さを順にa,b,c,d,e,f,gとすると、それぞれは互いに異なる。
  • min(b,d,f)＞max(a,c,e,g)またはmax(b,d,f)＜min(a,c,e,g)を満たす。

a,b,c,d,e,f,gの下限・上限が与えられる。
各門松は与えられた下限以上上限以下の整数の高さを取るとき、スーパーリッチ門松となる高さの組み合わせの数を答えよ。

解法

想定解法では、next_permutationで7本の高さの順序を総当たりする。
後は門松の高さを低い順に定め、その組み合わせ数を算出していく。
これは累積和を使うとO(max(Height))で済むDPとなる。
next_permutationでこのDPを7!通り(のうちmin(b,d,f)＞max(a,c,e,g)またはmax(b,d,f)＜min(a,c,e,g)を満たす組み合わせ)について行えばよい。


自分は包除原理で解いた。
まず、以下をそれぞれ求める。

  • x=min(b,d,f)となる異なるb,d,fの組み合わせ数up_even(x)
  • x=max(b,d,f)となる異なるb,d,fの組み合わせ数down_even(x)
  • x=min(a,c,e,g)となる異なるa,c,e,gの組み合わせ数up_odd(x)
  • x=max(a,c,e,g)となる異なるa,c,e,gの組み合わせ数down_odd(x)

するとx＜yとなる各x,yについてdown_even(x)*up_odd(y) + down_odd(x)*up_even(y)の和を求めればよい。
問題はup/downのそれぞれの求め方である。
例として４要素あって複雑なdown_odd(x)を考える。
まず、x=max(a,c,e,g)なのでa,c,e,gのどれが最大値になるかを４通り試す。
例えばx=aとする。すると、c,e,gはa未満でかつ互いに異なっていなければならない。
この数は包除原理に則り以下の計算で解ける。

  • まずc,e,gがとりうる値、すなわちa未満のc,e,gの取りうる数の積を加算する。
  • そこからc,e,gのうち２つ以上が一致する以下のケースを減算する。
    • cとeが一致する組み合わせとgの組み合わせの積
    • cとgが一致する組み合わせとeの組み合わせの積
    • eとgが一致する組み合わせとcの組み合わせの積
  • c,e,gのうち３全部が一致するケースは、上記処理で３回減算されてしまっているので、２回分加算しなおす。
int V[7][2];
ll mo=1000000007;
ll ret;
ll up[2][20200];
ll sup[2][20200];
ll down[2][20200];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>V[0][0]>>V[0][1];
	cin>>V[4][0]>>V[4][1];
	cin>>V[1][0]>>V[1][1];
	cin>>V[5][0]>>V[5][1];
	cin>>V[2][0]>>V[2][1];
	cin>>V[6][0]>>V[6][1];
	cin>>V[3][0]>>V[3][1];
	
	
	for(i=1;i<=20000;i++) {
		FOR(j,4) {
			int a=j%4, b=(j+1)%4, c=(j+2)%4, d=(j+3)%4;
			if(V[a][0]<=i && i<=V[a][1]) {
				ll B=max(0,min(i,V[b][1]+1)-V[b][0]);
				ll C=max(0,min(i,V[c][1]+1)-V[c][0]);
				ll D=max(0,min(i,V[d][1]+1)-V[d][0]);
				ll BC=max(0,min(i,min(V[b][1],V[c][1])+1)-max(V[b][0],V[c][0]));
				ll BD=max(0,min(i,min(V[b][1],V[d][1])+1)-max(V[b][0],V[d][0]));
				ll CD=max(0,min(i,min(V[c][1],V[d][1])+1)-max(V[c][0],V[d][0]));
				ll BCD=max(0,min(i,min(V[b][1],min(V[c][1],V[d][1]))+1)-max(V[b][0],max(V[c][0],V[d][0])));
				
				if(B&&C&&D) {
					down[0][i] += B*C*D;
					down[0][i] -= BC*D;
					down[0][i] -= CD*B;
					down[0][i] -= BD*C;
					down[0][i] += 2*BCD;
				}
				
				B=max(0,V[b][1]-max(i,V[b][0]-1));
				C=max(0,V[c][1]-max(i,V[c][0]-1));
				D=max(0,V[d][1]-max(i,V[d][0]-1));
				BC=max(0,min(V[b][1],V[c][1])-max(i,max(V[b][0],V[c][0])-1));
				BD=max(0,min(V[b][1],V[d][1])-max(i,max(V[b][0],V[d][0])-1));
				CD=max(0,min(V[c][1],V[d][1])-max(i,max(V[c][0],V[d][0])-1));
				BCD=max(0,min(V[b][1],min(V[c][1],V[d][1]))-max(i,max(V[b][0],max(V[c][0],V[d][0]))-1));
				if(B&&C&&D) {
					up[0][i] += B*C*D;
					up[0][i] -= BC*D;
					up[0][i] -= CD*B;
					up[0][i] -= BD*C;
					up[0][i] += 2*BCD;
				}
			}
		}
		
		FOR(j,3) {
			int a=j+4, b=(j+1)%3+4, c=(j+2)%3+4;
			if(V[a][0]<=i && i<=V[a][1]) {
				ll B=max(0,min(i,V[b][1]+1)-V[b][0]);
				ll C=max(0,min(i,V[c][1]+1)-V[c][0]);
				ll BC=max(0,min(i,min(V[b][1],V[c][1])+1)-max(V[b][0],V[c][0]));
				down[1][i] += B*C-BC;
				
				B=max(0,V[b][1]-max(i,V[b][0]-1));
				C=max(0,V[c][1]-max(i,V[c][0]-1));
				BC=max(0,min(V[b][1],V[c][1])-max(i,max(V[b][0],V[c][0])-1));
				up[1][i] += B*C-BC;
			}
		}
		
		down[0][i]=(mo+down[0][i]%mo)%mo;
		down[1][i]=(mo+down[1][i]%mo)%mo;
		up[0][i]=(mo+up[0][i]%mo)%mo;
		up[1][i]=(mo+up[1][i]%mo)%mo;
	}
	
	for(i=1;i<=20002;i++) sup[0][i]=(sup[0][i-1]+up[0][i])%mo;
	for(i=1;i<=20002;i++) sup[1][i]=(sup[1][i-1]+up[1][i])%mo;
		
	for(i=1;i<=20000;i++) {
		ret += (sup[0][20002]-sup[0][i])*down[1][i]%mo;
		ret += (sup[1][20002]-sup[1][i])*down[0][i]%mo;
		ret %= mo;
		ret += mo;
	}
	
	cout<<ret%mo<<endl;
	
}

まとめ

next_permutation解より実行は速い。
包除原理の部分をBitDPの要領で書けば、スーパーリッチ門松が9個や11個の門松で定義されていても間に合う。
O(2^N*max(height))だしね。next_permutation解はO(N!*max(height))でちょっと重い。