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; } };