Mがもう少し大きくても良かったりしないかな。
https://yukicoder.me/problems/no/1560
問題
N人の人がおり、M個の議題について賛成・反対という情報が与えられる。
これからM個の議題をある順番で議論する。
議論の際は残ったメンバーで多数決を取り、賛成が半数以上なら可決される。
その際、反対派はその場を去り以降の議論に参加しない。
議題の議論順M!通りのうち、全議題が可決されるのは何通りか。
解法
すでにいくつか議論がなされた場合、残された人はそれらの議論に賛成済みの人のみである。
その状態で、新たな議論を行った際、賛成が過半数がどうかを総当たりしよう。
bitDPの要領でO(M*4^M)かけて解ける。
int N,M; int C[1<<12]; ll dp[1<<12]; void solve() { int i,j,k,l,r,x,y; string s; cin>>N>>M; FOR(i,N) { x=0; FOR(j,M) { cin>>y; x=x*2+y; } C[x]++; } dp[0]=1; int mask,mask2; FOR(mask,1<<M) if(dp[mask]) { FOR(j,M) if((mask&(1<<j))==0) { int win=0,lose=0; FOR(mask2,1<<M) if((mask&mask2)==mask) { if(mask2&(1<<j)) win+=C[mask2]; else win-=C[mask2]; } if(win>=0) dp[mask|(1<<j)]+=dp[mask]; } } cout<<dp[(1<<M)-1]<<endl; }
まとめ
民主主義にあこがれる独裁者とは…。