[yukicoder] 裏表ちわーわ

シリーズ：掃き出し法について	URL
問題：十文字に反転して色を揃えて！(最短手数の最大化)	https://codeiq.jp/q/2972
single/OpenMP	https://qiita.com/cielavenir/items/2fa1f1149132de579a46
std::async	https://qiita.com/cielavenir/items/61b329936ef6508a5938
番外編：オンラインジャッジで並列実行は使えるか？	https://qiita.com/cielavenir/items/ade2b7c0b5a63b2687f0
問題：裏表ちわーわ(解の存在判定)	http://yukicoder.me/problems/no/460 https://www.codeeval.com/public_sc/191/
解説	https://qiita.com/cielavenir/items/c6b15ff4e28fb5f492ec

• 以下に進む前に、 まずCodeIQの問題の解説(single)をお読み下さい

---

• CodeIQの問題は、全ての盤面を列挙し、最短手数を求め、最大(の盤面)を出力する問題であった。

• 一方、この問題は特定の盤面の最短手数を求めるだけで良い。

• ただし、今度は解の存在判定が必要となる。

• 判定は、(左辺を解、右辺を問題とした時)右辺の掃き出しに失敗した行の左辺が0になっていれば良い。

  • この左辺を0解として扱って良い(親記事の更新参照)。

• ライツアウトでは吐き出しに失敗するのは終端であるが、このパズルでは途中で失敗する場合がある。

a=1x
b=0y
c=1z

• といった具合である。このため、吐き出しが失敗した行を記録したうえで、ひとまず先に進む操作が必要になる。

解答例

• CodeEvalのLights Outも同じソースで解けます。

  • ICPC2010 Regional D (Awkward Lights)も少しの変更で解けると思いますが、解の存在判定のみで手数は出力する必要が無いため、省略します。
  • よく考えたら整数じゃなくてbitset使わないといけないから大改造だったわ

• OpenMPの処理を入れてありますが、yukicoder(やおそらくCodeEval)では無視されますし、申し訳程度です。

tyama_yukicoder460_codeeval191.cpp

#pragma GCC optimize("O3")
#pragma GCC target("avx")

#include <vector>
#include <algorithm>
#include <cstdio>
using namespace std;

//#define CODEEVAL191

#ifdef CODEEVAL191
char str[999];
typedef __uint128_t val_t;
int popcnt(const val_t &x){int r=0;val_t z=x;for(;z;z/=2)r+=z%2;return r;}
#else
typedef unsigned long long val_t;
#define popcnt __builtin_popcountll
#endif

int lightsout(int x,int y){
	vector<vector<val_t>>a(x*y);
	for(int i=0;i<x*y;i++)a[i].resize(2);

	//create problem
	for(int i=0;i<x;i++){
		for(int j=0;j<y;j++){
			a[i+j*x][0]=(val_t)1<<(i+j*x);
			a[i+j*x][1]= 0 +
				((val_t)1<<(i+j*x)) |
				(i>0   ? (val_t)1<<(i-1+j*x) : 0) |
				(i<x-1 ? (val_t)1<<(i+1+j*x) : 0) |
				(j>0   ? (val_t)1<<(i+(j-1)*x) : 0) |
				(j<y-1 ? (val_t)1<<(i+(j+1)*x) : 0) |
#ifndef CODEEVAL191
				(i>0   && j>0   ? (val_t)1<<(i-1+(j-1)*x) : 0) |
				(i<x-1 && j>0   ? (val_t)1<<(i+1+(j-1)*x) : 0) |
				(i>0   && j<y-1 ? (val_t)1<<(i-1+(j+1)*x) : 0) |
				(i<x-1 && j<y-1 ? (val_t)1<<(i+1+(j+1)*x) : 0) |
#endif
				0;
		}
	}

	//solve
	val_t badbits=0;
	int i=0;
	for(;i<x*y;i++){
		if((a[i][1]&((val_t)1<<i))==0){
			int j=i+1;
			for(;j<x*y;j++){
				if((a[j][1]&((val_t)1<<i))!=0){
					swap(a[i],a[j]);
					break;
				}
			}
			if(j==x*y){
				badbits|=(val_t)1<<i;
				continue;
			}
		}

		for(int j=0;j<x*y;j++){
			if(i==j)continue;
			if((a[j][1]&((val_t)1<<i))!=0){
				a[j][0]^=a[i][0];
				a[j][1]^=a[i][1];
			}
		}
	}
	int k=x*y-popcnt(badbits);
	//fprintf(stderr,"quiet pattern=%d\n",x*y-k);

	//0解(quiet pattern)の集合tを用意する
	val_t tmsk=0;
	vector<val_t>t;
	vector<pair<int,val_t>>a_ok;
	for(int i=0;i<x*y;i++){
		if((badbits>>i)&1){
			t.push_back(a[i][0]);
		}else{
			a_ok.emplace_back(i,a[i][0]);
			tmsk|=(val_t)1<<i;
		}
	}

	//入力・解の存在判定
#ifdef CODEEVAL191
	scanf("%s",str);
#endif
	val_t input=0;
	for(int i=0;i<x*y;i++){
		int t;
#ifdef CODEEVAL191
		t=str[i%x+i/x*(x+1)]=='O';
#else
		scanf("%d",&t);
#endif
		input|=(val_t)t<<i;
	}
	if(any_of(t.begin(),t.end(),[&](val_t &e)->bool{
		return popcnt(e&input)&1;
	})){
		return -1;
	}

	vector<val_t>tlst(1<<(x*y-k)); // このメモリはあまり大きくならないはず
	for(val_t l=0;l<1<<(x*y-k);l++){
		val_t r=0;
		for(int j=0;j<x*y-k;j++)if(l&((val_t)1<<j))r^=t[j];
		tlst[l]=r;
	}

	val_t r0=1<<29;
	val_t c0=0;
	for(auto &j:a_ok)if(input&((val_t)1<<j.first))c0^=j.second;
	//0解の重ね合わせをすべて試す
	#pragma omp parallel for reduction(min:r0)
	for(val_t l=0;l<(val_t)1<<(x*y-k);l++){
		val_t r1=c0;
		//for(int j=0;j<x*y-k;j++)if(l&((val_t)1<<j))r1^=t[j];
		r1^=tlst[l];
		r0=min(r0,(val_t)popcnt(r1));
	}
	return r0;
}

int main(int argc, char **argv){
#ifdef CODEEVAL191
	if(argc>1)freopen(argv[1],"rb",stdin);
#endif
	int m,n;
	for(;~scanf("%d%d",&m,&n);){
		int r=lightsout(n,m);
		if(r<0){
#ifdef CODEEVAL191
			puts("Impossible");
#else
			puts("-1");
#endif
		}else{
			printf("%d\n",r);
		}
	}
}