kmjp's blog

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

TopCoder SRM 666 Div1 Medium SumOverPermutations

Codeforcesに出そう。
http://community.topcoder.com/stat?c=problem_statement&pm=13764

問題

N個の箱が一列に並んでおり、そこに任意の順でN色のボールのどれかを1個ずつ入れていく(各色のボールは十分にある)。
その際、隣同士の箱に同じ色のボールが入ってないようにしたい。

そのような入れ方の組み合わせを考える際、以下の間違った入れ方で考えていくとする。

  • ある箱にボールを入れる際、既に隣に1個ボールが入っているなら、それと異なる色を入れるのでその箱に入るボールの色は(N-1)通り。
  • ある箱にボールを入れる際、既に両隣に2個ボールが入っているなら、それと異なる色を入れるのでその箱に入るボールの色は(N-2)通り。
    • (なお、問題文中にあるとおりこの考え方は誤っている。両隣のボールの色が同じ場合を考慮していない)

上記誤った考え方でボールの色の組み合わせを考えるとする。
ボールの入れ方の順番をN!全通り試す場合、N!通りにおけるボールの色の組み合わせの和を求めよ。

解法

x個の連続した空き箱があり、かつそのx個の片隣、または両隣にボールが配置済みの場合、それらの空き箱の埋め方の組み合わせ数H(x), F(x)とする。
x=1~N-1まで順にDPでH(x), F(x)を求めていく。

例えばH(x)を求める場合、1~x番が空き箱で(x+1)番にボールが入っていると考える。
次にi番目にボールを入れる場合、残った箱の状態は(i-1)個の片隣にボールの入った箱と、(x-i)個の両隣にボールが入った箱の組み合わせが出る。
この両連続箱群のボールの埋め方はそれぞれH(i-1)、F(x-i)通りである。
また、残り(x-1)個の空き箱のうち(i-1)回は1~(i-1)番側の箱、(x-i)回は(i+1)~(x-i)番側の箱にボールを入れる。
よって H(x) += H(i-1)\times F(x-i) \times {}_{x-1} C_{i-1}といったようにDP出来る。
F(x)も同じ考え方でDP出来る。

最後に元の問題であるN個の空き箱の両隣にボールがない場合の組み合わせだが、ボールを1個置けば片隣にボールが埋まっている連続箱群2つの組にできるので、sum(F(i-1)*F(N-i))で求められる。

ll mo=1000000007;
ll hc[4040];
ll fc[4040];
const int CN=4001;
ll C[CN][CN];

class SumOverPermutations {
	public:
	int findSum(int n) {
		ZERO(hc);
		ZERO(fc);
		int i,j;
		
		FOR(i,CN) for(j=0;j<=i;j++) C[i][j]=(j==0||j==i)?1:(C[i-1][j-1]+C[i-1][j])%mo;
		
		hc[0]=fc[0]=1;
		hc[1]=n-1;
		fc[1]=n-2;
		
		for(i=2;i<n;i++) {
			FOR(j,i) {
				// half close
				if(j==0) hc[i] += (n-1)*hc[i-1]%mo;
				else hc[i] += n*fc[j]%mo*hc[i-1-j]%mo*C[i-1][j]%mo;
				//full close
				if(j==0||j==i-1) fc[i] += (n-1)*fc[i-1]%mo;
				else fc[i] += n*fc[j]%mo*fc[i-1-j]%mo*C[i-1][j]%mo;
			}
			hc[i]%=mo;
			fc[i]%=mo;
		}
		
		ll ret=0;
		FOR(i,n) {
			if(i==0 || i==n-1) ret += n*hc[n-1]%mo;
			else ret += n*hc[i]%mo*hc[n-1-i]%mo*C[n-1][i]%mo;
		}
		return ret%mo;
	}
}

まとめ

本番はCombinationの分を最初考慮し忘れたが、すぐに思い出せて良かった。
450pt相当の問題かな?