kmjp's blog

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

第5回 ドワンゴからの挑戦状 本戦 : D - Parentheses Inversions

その他コンテスト

Cに続きDも知らない解法が出てきて勉強になります。
https://atcoder.jp/contests/dwacon5th-final-open/tasks/dwacon5th_final_d

問題

'('')'が同数からなるN文字の文字列Sが与えられる。
1～NのPermutation Pのうち、SをPに応じて位置を置換したとき、正しい括弧列となるPにおける転倒数の総和を求めよ。

解法

M=N/2とする。
元のSにおける閉じ括弧と開き括弧の転倒数をIとする。
理由はEditorialを見てもらうとして、解はIと線形の関係にありA(M)+B(M)*Iとなる。

A(M)とB(M)はMで定まる値である。
そこで、両極端な例からA(M)、B(M)を求めよう。
I=0、すなわちS='((('...')))'の時の解がA(M)、その正反対の時のS=')))'...'((('の解がA(M)+B(M)*M^2となる。
ここからA(M),B(M)を求めよう。

ここでは前者のケースのみ説明する。後者の場合漸化式がちょっと変わるだけで式にはない。
S='((('...')))'をPで置換した後、正しい括弧列である場合の(括弧ではなくPの)転倒数を考えよう。
'('同士、および')'同士の転倒数は、確率1/2で転倒すると考えると容易に求められる。
問題は')'と'('の転倒数である。

  • C(m) := m番目のカタラン数
  • D(m) := m個の開き括弧と閉じ括弧が正しい括弧列を成すケースにおける、開き括弧と閉じ括弧の転倒数の総和

よって、D(m)を求めたい。
D(m)を考える際、最初の開き括弧に対応する閉じ括弧までに2i文字あるケースを考えると
\displaystyle D(m) = \sum_{i=1}^{m} (C(i-1)D(m-i)+C(m-i)D(i-1)+i(m-i)C(i-1)C(m-i)
となる。Editorialでは、sumの中の最初の２つの積和を一旦ばらしてまとめ、
\displaystyle D(m) = \sum_{i=1}^{m} (2C(m-i)D(i-1)+i(m-i)C(i-1)C(m-i)
としている(C(a)D(b)!=C(b)D(a)なので、元のsumの中は直接くっつけることはできない。)

これでO(N^2)で求められることになるが、当然これはTLEする。
解のmod 10^9+7を求めたいので、フーリエ変換に持ち込むのも厳しい。
そこでD(m)、C(m)の母関数を考え式変形する。
P(t) = \sum_i C(i)t^i, Q(t) = \sum_i D(i)t^iとなすると、先ほどの式から Q(t)=2tQ(t)P(t)+t^2(tP(t))'P'(t)となる。
式変形して Q(t)=\frac{t^2(tP(t))'P'(t)}{1-2tP(t)}になる。ここで、Wikipediaのカタラン数の項目に母関数P(t)の一般項 P(t)=\frac{1-\sqrt(1-4t)}{2t}を代入しよう。

すると Q(t)=\frac{t^2P'(t)}{1-4t}となる。P(t)はCombinationを使い容易に計算できるので、多項式を(1-4t)で割っていくことを考えるとQ(t)の各項が全部でO(N)で求められる。

以下、コメントアウト部分は元のO(N^2)解法である。

int N,M;
string S;
ll mo=1000000007;
const int NUM_=1400001;
ll fact[NUM_+1],factr[NUM_+1],inv[NUM_+1];
ll D[505050],D2[505050];

ll comb(ll N_, ll C_) {
	if(C_<0 || C_>N_) return 0;
	return factr[C_]*fact[N_]%mo*factr[N_-C_]%mo;
}
ll catalan(int n) {
	return fact[2*n]*factr[n]%mo*factr[n+1]%mo;
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	inv[1]=fact[0]=factr[0]=1;
	for (int i=2;i<=NUM_;++i) inv[i] = inv[mo % i] * (mo - mo / i) % mo;
	for (int i=1;i<=NUM_;++i) fact[i]=fact[i-1]*i%mo, factr[i]=factr[i-1]*inv[i]%mo;
	
	cin>>N>>S;
	M=N/2;
	
	/*
	D[1]=0;
	D2[1]=1;
	for(i=2;i<=M;i++) {
		for(j=1;j<=i;j++) {
			(D[i]+=catalan(i-j)*D[j-1]+catalan(j-1)*D[i-j]+1LL*j*(i-j)%mo*catalan(j-1)%mo*catalan(i-j))%=mo;
			(D2[i]+=catalan(i-j)*D2[j-1]+catalan(j-1)*D2[i-j]+(2*(j-1)+1+1LL*j*(i-j))%mo*catalan(j-1)%mo*catalan(i-j))%=mo;
		}
	}
	*/
	for(i=2;i<=M;i++) D[i]=(i-1)*catalan(i-1)%mo;
	FOR(i,M+1) (D[i+1]+=4*D[i])%=mo;
	FOR(i,M+1) D2[i]=((catalan(i)*i%mo*i-D[i])%mo+mo)%mo;

	ll Am=(1LL*M*(M-1)/2%mo*catalan(M)+D[M])%mo*fact[M]%mo*fact[M]%mo;
	ll AmpBm=(1LL*M*(M-1)/2%mo*catalan(M)+D2[M])%mo*fact[M]%mo*fact[M]%mo;
	ll Bm=(AmpBm-Am+mo)%mo*((inv[M]*inv[M])%mo)%mo;
	
	ll rev=0,sum=0;
	FORR(c,S) {
		if(c==')') rev++;
		else sum+=rev;
	}
	cout<<(Am+Bm*(sum%mo))%mo<<endl;
}

まとめ

これはどこもかしこも思いつく気がしない…。