kmjp's blog

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

Codeforces #684 Div1 D. INOI Final Contests

ややこしいDP。
http://codeforces.com/contest/1439/problem/D

問題

整数N,Mが与えられる。
1~Nの番号を持つN台のPCが左右1列に並んでいる。
ここで、M人の生徒がこれらを利用することになるが、各生徒iには2つのパラメータA[i]とB[i]を持つ。
生徒は1番の生徒から順にきて、以下のようにPCを利用する。

  • B[i]は左右のいずれかを示す。各生徒は、B[i]の側から反対側に向けて移動し、A[i]番目のPCの前で止まる。
  • ただし、A[i]番目のPCの前に、それ以前に来た生徒が止まっている場合、そこを超えてその先の最初の未使用PCの前で止まる。
  • もし未使用PCがなく反対側の端まで移動してしまった場合、そのパラメータは無効とする。

有効なパラメータ全通りについて、各生徒iが停止したPC番号をC[i]としたとき、|A[i]-C[i]|の総和を求めよ。

解法

まずN=Mの時を考える。
dp1(i) := N=M=iの時の、有効なパラメータの組み合わせ
dp2(i) := N=M=iの時の、有効なパラメータの組み合わせにおける|A[j]-C[j]|の総和

dp1(i)は、最後の人がj番目の席に座るケースを考えると(i+1)*dp1(j-1)*dp1(i-j)*comb(i-1,j-1)通り考えられる。
jを総当たりすればO(N^2)でdp1(N)を求められる。
dp2(i)も最後の人がj番目に座るケースを考えると計算できる。

次にN>Mの時を考える。
dp3(i,j) := N=i、M=jの時の有効なパラメータの組み合わせ
dp4(i,j) := N=i、M=jの時の有効なパラメータの組み合わせにおける|A[k]-C[k]|の総和

dp3の計算では、空き席を挟みながら、連続して占有された領域を配置することを考えると、dp1を用いて計算していくことができる。
dp4の計算も、dp3とdp2の計算方法を組み合わせて計算できる。

ll mo;
struct modint {
	ll v;
	modint(const ll a=0) { v=a; if(mo&&(v>=mo||v<0)) v=(v%mo+mo)%mo;}
	static modint pow(const modint& a,ll n=mo-2) {
		ll b=a.v,r=1;
		while(n) r=r*((n%2)?b:1)%mo,b=b*b%mo,n>>=1;
		return modint(r);
	}
	modint& operator+=(const modint& a) { v+=a.v; if(v>=mo) v-=mo; return *this;}
	modint& operator-=(const modint& a) { v+=mo-a.v; if(v>=mo) v-=mo; return *this;}
	modint& operator*=(const modint& a) { v=v*a.v%mo; return *this;}
	modint& operator/=(const modint& a) { assert(a.v!=0); *this*=pow(a); return *this;}
	modint operator+(const modint& a) const { modint res(*this); return res+=a;}
	modint operator-(const modint& a) const { modint res(*this); return res-=a;}
	modint operator*(const modint& a) const { modint res(*this); return res*=a;}
	modint operator/(const modint& a) const { modint res(*this); return res/=a;}
	friend ostream& operator<<(ostream& os, const modint& a){ os<<a.v; return os;}
};

int N,M;
modint dp1[505];
modint dp2[505];
modint dp3[505][505];
modint dp4[505][505];

ll comb(ll N_, ll C_) {
	const int NUM_=400001;
	static ll fact[NUM_+1],factr[NUM_+1],inv[NUM_+1];
	if (fact[0]==0) {
		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;
	}
	if(C_<0 || C_>N_) return 0;
	return factr[C_]*fact[N_]%mo*factr[N_-C_]%mo;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M>>mo;
	dp1[0]=1;
	for(i=1;i<=N;i++) {
		for(j=1;j<=i;j++) {
			dp1[i]+=modint(i+1)*dp1[j-1]*dp1[i-j]*comb(i-1,j-1);
			dp2[i]+=modint(i+1)*(dp2[i-j]*dp1[j-1]+dp1[i-j]*dp2[j-1])*comb(i-1,j-1);
			dp2[i]+=dp1[j-1]*dp1[i-j]*comb(i-1,j-1)*(comb(j-1+1,2)+comb(i-j+1,2));
		}
	}
	dp3[0][0]=1;
	for(i=1;i<=N;i++) {
		FOR(j,i) {
			dp3[i][j]=dp3[i-1][j];
			dp4[i][j]=dp4[i-1][j];
			for(l=1;l<=j;l++) {
				dp3[i][j]+=dp1[l]*dp3[i-l-1][j-l]*comb(j,l);
				dp4[i][j]+=(dp1[l]*dp4[i-l-1][j-l]+dp2[l]*dp3[i-l-1][j-l])*comb(j,l);
			}
		}
		dp3[i][i]=dp1[i];
		dp4[i][i]=dp2[i];
	}
	
	cout<<dp4[N][M]<<endl;
	
	
	
}

まとめ

こういうDP、さっと組める気がしないな。