kmjp's blog

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

yukicoder : No.1560 majority x majority

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

まとめ

民主主義にあこがれる独裁者とは…。