kmjp's blog

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

yukicoder : No.2236 Lights Out On Simple Graph

ちょっと戸惑った。
https://yukicoder.me/problems/no/2236

問題

N頂点M辺のグラフがある。
各点は白黒のいずれかで塗られている。

辺を1つ選び、両端の頂点の色を白黒反転させることができるとき、全頂点を白色にできるか判定せよ。
できるなら最小選択回数を示せ。

解法

Mが小さいので、半分全列挙で解く。
先頭floor(M/2)通りの辺の選択法を総当たりし、その結果の各頂点の色と、対応する操作回数の最小値のmapを持とう。

あとは後半ceil(M/2)通りの辺の選択法を総当たりし、先頭の辺の総当たり結果と合わせて全点白色にできるケースの最小操作回数を求める。

int N,M;
int A[40],B[40];
ll BM;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,M) {
		cin>>A[i]>>B[i];
		A[i]--,B[i]--;
	}
	FOR(i,N) {
		cin>>x;
		BM|=((ll)x)<<i;
	}
	int mask;
	int ret=100;
	map<ll,int> memo;
	int L=M/2,R=M-L;
	FOR(mask,1<<L) {
		ll CM=BM;
		int step=0;
		FOR(i,L) if(mask&(1<<i)) {
			CM^=1LL<<A[i];
			CM^=1LL<<B[i];
			step++;
		}
		if(memo.count(CM)==0) memo[CM]=100;
		chmin(memo[CM],step);
	}
	FOR(mask,1<<R) {
		ll CM=0;
		int step=0;
		FOR(i,R) if(mask&(1<<i)) {
			CM^=1LL<<A[L+i];
			CM^=1LL<<B[L+i];
			step++;
		}
		if(memo.count(CM)) ret=min(ret,memo[CM]+step);
	}
	
	
	
	if(ret==100) ret=-1;
	cout<<ret<<endl;
}

まとめ

半分全列挙、地味に実装苦手なんだよな。
もっとサラッと書けないかな。