kmjp's blog

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

yukicoder : No.1685 One by One

yukicoder

なるほど…。
https://yukicoder.me/problems/no/1685

問題

N要素の整数列Aがあり、初期状態で全要素0である。
以下の処理をちょうどM回繰り返したとき、構成できる数列は何通りか。

  • 隣接する2要素を選び、片方インクリメントして片方デクリメントする。
  • なお、隣接する2要素として、先頭と末尾を選んでも良い。

解法

A[i]=B[(i+1)%N]-B[i]となる数列Bを考える。
上記処理は、B[i]の単一要素をインクリメントまたはデクリメントしたものとなる。
あいにくB[i]とA[i]は1対1対応しない。B[i]の全要素に同じ定数を加えると、同じA[i]ができてしまうためである。
そこで、有効なB[i]とは、B[i]の中央値が0のものだけをいうこととする。こうするとAとBは1対1対応となる。

あとはBを数え上げることを考える。
Bのうち、負・0・正の値を取る要素がm,z,p個あったとする。
Bの中央値が0という条件より、(m,z,p)のうち有効な組み合わせは限られる。

事前に
f(n,m) := 異なるn箱に、m個の区別できないボールを入れたとき、各箱最低1個のボールが入る入れ方
を計算しておくと、(m,z,p)に対し、最小デクリメント・インクリメント合計数xで達成するような数列Bを数え上げることができる。
問題は、処理回数がMちょうどであることである。

  • xとMのパリティが一緒な場合、インクリメントとデクリメントを交互に行えば、同じ数列BをM回の処理で構築できる。
  • そうでない場合、かつNが奇数の場合
    • B全体をインクリメントまたはデクリメントし、xとMのパリティを一致させよう。
    • もしB全体をインクリメントする場合、z+p-m回余分な処理が必要(mが減算なのは、デクリメント回数を減らせるため)
    • もしB全体をデクリメントする場合、z+m-p回余分な処理が必要(pが減算なので、インクリメント回数を減らせるため)
    • よってx+z+p-mがM以下なら、同じ数列BをM回の処理で構築できる

(m,z,p)を総当たりするとO(N^2)かかり、xの総当たりは行えない。
ただ、有効なxは偶奇毎に、それぞれある区間となるので、うまく累積和を取ることでxの総当たりを(m,z,p)の後のタイミングにずらすことができる。

int N,M;
ll dp[4040][4040];
ll dp2[4040][4040];
const ll mo=1000000007;

ll comb(int P_,int Q_) {
	static const int N_=4020;
	static ll C_[N_][N_];
	
	if(C_[0][0]==0) {
		int i,j;
		FOR(i,N_) C_[i][0]=C_[i][i]=1;
		for(i=1;i<N_;i++) for(j=1;j<i;j++) C_[i][j]=(C_[i-1][j-1]+C_[i-1][j])%mo;
	}
	if(P_<0 || P_>N_ || Q_<0 || Q_>P_) return 0;
	return C_[P_][Q_];
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	dp[0][0]=1;
	cin>>N>>M;
	FOR(i,N) {
		FOR(j,4020) dp[i+1][j+1]=(dp[i][j]+dp[i+1][j])%mo;
	}
	
	ll ret=0;
	for(int mi=0;mi<=N;mi++) {
		for(int ze=0;mi+ze<=N;ze++) {
			int pl=N-mi-ze;
			if(mi>=(N+1)/2) continue;
			if(mi+ze<(N+1)/2) continue;
			
			ll pat=comb(mi+ze,mi)*comb(N,pl)%mo;
			if((mi+pl)%2==M%2) {
				dp2[mi+pl][mi+pl]+=pat;
				if(N%2) {
					int d=mi+pl+1;
					int ma=M-(ze-abs(pl-mi));
					if(d%2!=ma%2) ma--;
					if(d<=ma) {
						dp2[mi+pl][d]+=pat;
						dp2[mi+pl][ma+2]+=mo-pat;
					}
				}
			}
			else {
				dp2[mi+pl][mi+pl+1]+=pat;
				if(N%2) {
					int d=mi+pl;
					int ma=M-(ze-abs(pl-mi));
					if(d%2!=ma%2) ma--;
					if(d<=ma) {
						dp2[mi+pl][d]+=pat;
						dp2[mi+pl][ma+2]+=mo-pat;
					}
				}
				
			}
		}
	}
	FOR(i,N+1) {
		FOR(j,M+1) {
			if(j>=2) (dp2[i][j]+=dp2[i][j-2])%=mo;
			(ret+=dp2[i][j]*dp[i][j])%=mo;
		}
	}
	cout<<ret%mo<<endl;
	
}

まとめ

うまい標準形を探すの、なんかコツあるのかな。