kmjp's blog

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

Indeedなう（本選A） : F - 就職活動

その他コンテスト

これは自力では解けなかった。
http://indeednow-finala-open.contest.atcoder.jp/tasks/indeednow_2015_finala_f

問題

X人の人がおり、それぞれS,N,K社の３つの会社への就職希望の有無を尋ねた。
３つの会社にはそれぞれS人・N人・K人まで就職できる。

各人の就職希望は(2^3)通りあるので、X人全体では就職希望の組み合わせは(2^3X)通りある。
各人を３社のどれかに就職させるとき、全員の希望を満たせる組み合わせは何通りか。

解法

自力では解けなかったのでEditorialを参考にして解いた。
http://www.slideshare.net/chokudai/indeednow-finala

ホールの定理を使いつつ、半分全列挙風に７つの変数の範囲を定めていく。
何処も希望しない人がいる場合は当然全員の希望は満たせない。
よって、X人を以下の7通りに分類するとする。 (X_s + X_n + X_k + X_{sn} + X_{nk} + X_{ks} + X_{snk} = X)

  • X_s, X_n, X_k : それぞれS,N,K社のみに就職を希望する人の人数
  • X_{sn}, X_{nk}, X_{ks} : それぞれSとN,NとK,KとSの2社に就職を希望する人の人数
  • X_{snk} : ３社どれでも就職を希望する人の人数

これらの計X人を３社に振り分けることになる。
ここで各人の希望と会社の就職のマッチング関係を最大フローで表すと、ホールの定理より以下の条件を全て満たせば全員の希望を満たす組みあわせがある。

  • X_s \le S
  • X_n \le N
  • X_k \le K
  • X_s + X_n + X_{sn} \le S + N
  • X_n + X_k + X_{nk} \le N + K
  • X_k + X_s + X_{ks} \le K + S
  • X_s + X_n + X_k + X_{sn} + X_{nk} + X_{ks} + X_{snk} \le S+N+K

さすがに７変数でこの不等式を解くのは難しい。
そこで４変数分は総当たりし、残り３変数分は前処理で解くことを考える。
X_s, X_n, X_k, X_{sn}の４変数は総当たりするとすると、上記不等式でこれらは定数と考えられるので、残された変数に対し以下の関係が成り立つ。

  • X_{nk} \le C_1 = N + K - (X_n + X_k)
  • X_{ks} \le C_2 = K + S - (X_k + X_s)
  • X_{nk} + X_{ks} + X_{snk} = C_3 = X -(X_s + X_n + X_k + X_{sn} + X_{nk})

上記式より、 C_1, C_2, C_3に対して条件を満たす X_{nk}, X_{ks}, X_{snk}の数の組み合わせ数 F(C_1,C_2,C_3)を求めることができる。
C_1, C_2に関する式が不等式でなく等式である場合、 X_{nk}, X_{ks}, X_{snk}の数の組み合わせ数 G(C_1,C_2,C_3)は G(C_1,C_2,C_3) = \frac{C_3!}{C_1!C_2!C_3!}が成り立つ。
後はこの G(C_1,C_2,C_3)を累積和の要領で足していけば、 \displaystyle F(C_1,C_2,C_3) = \sum_{0 \le i \le C_1} \sum_{0 \le j \le C_2} G(i,j,C_3)を求めることができる。

最後に、 X_s, X_n, X_k, X_{sn}を総当たりしつつ F(C_1,C_2,C_3)の総和を求めればよい。
X,S,N,Kは150以下だが、 C_1, C_2は300まで行くので注意。

int X,S,N,K;
ll mo=1000000007;

ll fact[200],factr[200];
ll dp[355][355][200];
ll ret;

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

ll modpow(ll a, ll n = mo-2) {
	ll r=1;
	while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1;
	return r;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	int Nx,Ny,Nz,Nxy;
	
	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>>X>>S>>N>>K;
	fact[0]=factr[0]=1;
	FOR(i,199) fact[i+1]=fact[i]*(i+1)%mo, factr[i+1]=modpow(fact[i+1]);
	
	for(i=0;i<=X;i++) {
		FOR(x,301) FOR(y,301) {
			ll& t=dp[x][y][i];
			if(i-x-y>=0) t = fact[i]*factr[x]%mo*factr[y]%mo*factr[i-x-y]%mo;
			if(x) t += dp[x-1][y][i];
			if(y) t += dp[x][y-1][i];
			if(x&&y) t -= dp[x-1][y-1][i];
			if(t<0) t+= mo;
			while(t>=mo) t-= mo;
		}
	}
	
	if(S+N+K>=X) {
		FOR(Nx,min(X,S)+1) FOR(Ny,min(X-Nx,N)+1) FOR(Nz,min(X-Nx-Ny,K)+1) FOR(Nxy,X-Nx-Ny-Nz+1) {
			if(Nx+Ny+Nxy>S+N) break;
			ll pat=C[X][Nx]*C[X-Nx][Ny]%mo*C[X-Nx-Ny][Nz]%mo*C[X-Nx-Ny-Nz][Nxy]%mo;
			ret += pat * dp[N+K-Ny-Nz][S+K-Nx-Nz][X-Nx-Ny-Nz-Nxy] % mo;
		}
	}
	
	cout<<ret%mo<<endl;
}

まとめ

ホールの定理なんて知らなかったし、知ってても7変数を半々で処理していくなんて思いつかないわ。