TPC追いコン : B - ライツアウト

B→C→D→Eと段々簡単になっていった…？
http://oidashi.contest.atcoder.jp/tasks/oidashi_b

問題

H*W個の矩形状に並んだ電球からなるいわゆるライツアウトゲームを考える。
一部のボタンは押すことができない(隣のボタンを押すことで、点灯状態を変えることはできる。)

初期の電球の状態と、押せないボタンの一覧が与えられる。
全ての電球を消すのに必要な最小ボタン押下数を求めよ。

解法

最上位の押し方を決めると、２段目以降の押し方は一意に決まる(上の段の電球を消しきるように押すしかない)。
よって最上位の押し方を総当たりし、後は順次２段目以降を押していく。
その際

• 押せないボタンを押さずに済む
• 最終的に最下段の電球も消しきれる

のであれば、そのような押し方は題意の条件を満たすので、その場合の押下数最小値を求めよう。

前処理でボタン押下時の電球の変化を求めておくと、全体でO(H*2^W)ですむ。
Wが大きい場合は盤面を90度回転しよう。
H*Wが400以下なので、HかWのどちらかは20以下である。

int H,W,N;
int A[400][400];
int dis[400][400];
int pat[1<<21];
int row[404];
int ng[404];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>H>>W;
	FOR(y,H) FOR(x,W) cin>>A[y][x];
	cin>>N;
	FOR(i,N) {
		cin>>x>>y;
		dis[y][x]=1;
	}
	
	if(W>H) {
		FOR(y,400) FOR(x,y) swap(A[y][x],A[x][y]),swap(dis[y][x],dis[x][y]);
		swap(W,H);
	}
	assert(W<=20);
	
	FOR(y,H) FOR(x,W) row[y] |= A[y][x]<<x, ng[y] |= dis[y][x]<<x;
	
	
	int mask;
	FOR(mask,1<<W) {
		int x=0;
		FOR(i,W) if(mask&(1<<i)) pat[mask] ^= 7<<i;
		pat[mask]>>=1;
		pat[mask]&=(1<<W)-1;
	}
	
	int mi=1<<30;
	FOR(mask,1<<W) if((mask&ng[0])==0) {
		int cnt=__builtin_popcount(mask);
		int cur=row[0]^pat[mask];
		int nex=row[1]^mask;
		for(y=1;y<H;y++) {
			int nmask=cur;
			if(nmask&ng[y]) break;
			cur=nex^pat[nmask];
			nex=row[y+1]^nmask;
			cnt+=__builtin_popcount(nmask);
		}
		if(y==H && cur==0) mi=min(mi,cnt);
	}
	cout<<mi<<endl;
	
}

まとめ

本番最初計算量の目測を誤りO(H*2^(2W))と勘違いした。
そのため連立方程式に持ち込んで行列のランクを計算したりと非常にタイムロスしてしまった。