TopCoder SRM 356 Div1 Medium MarriageProblemRevised

問題

n人の男とm人の女がいる。
それぞれの男と女が"好きであるかどうか"の関係が与えられる。


この男女が以下の条件を満たすように結婚する。

  • 一人の男は、複数人の女と結婚できる。ただし、二人以上の女と結婚した場合、相手の女は自分以外の男と結婚していてはならない。
  • 一人の女は、複数人の男と結婚できる。ただし、二人以上の男と結婚した場合、相手の男は自分以外の女と結婚していてはならない。
  • 男と女が"好きである"関係にある男女のみが結婚できる。
  • すべての人が誰かと結婚している。


このとき、結婚の数を最小にしたい。
結婚の数の最小値を求めよ。

制約条件

n,m≦12

方針

オーダーの怪しい嘘DPで通した。
3進法で、それぞれの桁をm番目の女に対応させる。
桁が0のとき、結婚相手がいない。
桁が1のとき、「他に自分以外の結婚相手がいない男」と結婚している
桁が2のとき、「他に自分以外の結婚相手がいる男」と結婚している


ことを表す。
dp[i][mask]を、i番目まで男を見終えた後で、女の状態がmaskであるような状態での、結婚の数の最小値とする。


ここから、i番目の男の結婚の仕方を全通り試して表を更新するようなDPをした。


Editorialの解法はまだ理解していないので要復習。

ソースコード

最大ケース1.9sとか。超ギリギリ

int two[1<<15];
int dp[2][600000];

class MarriageProblemRevised {
	public:
	int neededMarriages(vector <string> pr) 
	{
		int n=pr.size(), m=pr[0].size(), pw[15];
		pw[0]=1;
		rep(i,14)pw[i+1]=pw[i]*3;
		rep(i,1<<15){
			two[i]=0;
			rep(j,15)if(i&1<<j)two[i]+=pw[j]*2;
		}
		
		rep(i,pw[m])dp[0][i]=inf;
		dp[0][0]=0;
		int cur=0,next=1;
		rep(i,n){
			rep(j,pw[m])dp[next][j]=inf;
			rep(mask,pw[m])if(dp[cur][mask]!=inf){
				//一人と
				int cand=0;
				rep(j,m)if(mask/pw[j]%3<2&&pr[i][j]=='1'){
					int nmask=mask-mask/pw[j]%3*pw[j]+pw[j], ncost=dp[cur][mask];
					if(mask/pw[j]%3==0)cand|=1<<j, ncost++;
					dp[next][nmask]=min(dp[next][nmask],ncost);
				}
				//複数と
				for(int j=cand;j;j=j-1&cand){
					dp[next][mask+two[j]]=min(dp[next][mask+two[j]],dp[cur][mask]+1);
				}
			}
			swap(cur,next);
		}
		int ans=inf;
		rep(i,pw[m]){
			rep(j,m)if(i/pw[j]%3==0)goto FAIL;
			ans=min(ans,dp[cur][i]); FAIL:;
		}
		return ans==inf?-1:ans;
	}
};