kmjp's blog

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

Codeforces #418 Div2 E. An unavoidable detour for home

一応解けてよかった。
http://codeforces.com/contest/814/problem/E

問題

要素が2か3の配列Dが与えられる。
以下の無向グラフは何通りあるか。

  • 頂点vの次数はD[v]
  • 頂点vから頂点0への距離をL(v)とすると、L(v)を並べた数列は昇順
  • 頂点vから頂点0への最短路は1通りしかない

解法

O(|D|^5)位のDPで解いた。

頂点0から順に、自身より番号の小さい頂点のうちどれにつなぐかを考えていく。
余った分は後でより大きな番号の頂点から接続しに来るかもしれないので余らせておく。
f(i,A2,A1,B2,B1) := 頂点iまで処理した段階で、頂点0までの距離が最遠の点のうち、未接続の辺が2個ある頂点がB2個、1個ある頂点がB1個、最遠点より1距離が短い点のうち未接続の辺が2個ある頂点がA2個、1個ある頂点がA1個あるような状態の組み合わせ

  • L(i)==L(i-1)となる場合
    • iからA2かA1に相当する頂点のいずれか1個に接続する。また、B2,B1に相当する頂点に任意個接続できる
  • L(i)==L(i-1)+1となる場合
    • A2=A1=0の場合のみ可能。iからB2かB1に相当する頂点のいずれか1個に接続する。
    • A2かA1に相当する頂点が余ると、あとでそこにつないだ頂点jが存在するとL(j)=L(i-1)<L(i)となるので不可
int N;
int D[51];
ll from[51][51][51][51];
ll to[51][51][51][51];
ll mo=1000000007;

const int CN=101;
ll C[CN][CN];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	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;
	
	cin>>N;
	FOR(i,N) cin>>D[i];
	
	from[D[0]==3][D[0]==2][D[1]==3][D[1]==2]=1;
	int a2,a1,b2,b1;
	
	for(i=2;i<N;i++) {
		ZERO(to);
		FOR(a2,N) FOR(a1,N) FOR(b2,N) if(a1+a2+b2<=N) FOR(b1,N) if(from[a2][a1][b2][b1]) {
			ll tmp=from[a2][a1][b2][b1];
			int y2,y1;
			if(a2 || a1) {
				for(y2=0;y2<=b2&&y2<=D[i]-1;y2++) for(y1=0;y1<=b1&&y2+y1<=D[i]-1;y1++) {
					ll Y=C[b2][y2]*C[b1][y1]%mo;
					int left=D[i]-1-y2-y1;
					if(a2) (to[a2-1][a1+1][b2-y2+(left==2)][b1-y1+y2+(left==1)] += a2*Y%mo*tmp)%=mo;
					if(a1) (to[a2][a1-1][b2-y2+(left==2)][b1-y1+y2+(left==1)] += a1*Y%mo*tmp)%=mo;
				}
			}
			else {
				if(b2) (to[b2-1][b1+1][D[i]==3][D[i]==2] += b2*tmp)%=mo;
				if(b1) (to[b2][b1-1][D[i]==3][D[i]==2] += b1*tmp)%=mo;
			}
		}
		
		
		swap(from,to);
	}
	cout<<from[0][0][0][0]<<endl;
}

まとめ

計算量が心配だけど一応通った。