十文字に反転して色を揃えて！(std::async)

シリーズ：掃き出し法について	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

(概要等はsingle/OpenMP版を参照下さい)

• 今まで並列プログラミングにはOpenMPを使ってきたが、std::asyncをvectorに突っ込むことでもできるらしいので、やってみた。

tyama_codeiq2972_async.cpp

// async
// 5 5: 0.08s
// 3 9: 1.47s
// 5 6: 15.53s
// 4 8: 83.18s
// 6 6: 772.15s

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

typedef unsigned long long val_t;
#define popcnt __builtin_popcountll
//typedef unsigned int val_t;
//#define popcnt __builtin_popcount
//typedef mpz_class val_t;
//int popcnt(const val_t &x){int r=0;val_t z=x;for(;z;z/=2)r+=z%2;return r;}

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

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

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

	//全盤面に対し最短手数を計算する
	int num_threads=thread::hardware_concurrency();
	auto f=[&](val_t start)->int{
		int r=0;
		for(val_t i_=start;i_<(val_t)1<<k;i_+=num_threads){
			//i_のiterationは本来はbadbitsを除いたビット
			//ライツアウトではbadbitsは末端に集中しているためこれで良い
			//本来はtlist/a_okのビットをbadbits以外に詰めるのが正解

			if(popcnt(i_)*2>k)continue;
			//完全反転についても求め、最小値を取る
			int c=1<<29;
			for(val_t i:{i_,i_^tmsk}){
				val_t r0=0;
				for(auto &j:a_ok)if(i&((val_t)1<<j.first))r0^=j.second;
				//0解の重ね合わせをすべて試す
				int c0=1<<29;
				for(val_t l=0;l<(val_t)1<<(x*y-k);l++){
					val_t r1=r0;
					//for(int j=0;j<x*y-k;j++)if(l&((val_t)1<<j))r1^=t[j];
					r1^=tlst[l];
					c0=min(c0,popcnt(r1));
				}
				c=min(c,c0);
			}
			r=max(r,c);
		}
		return r;
	};
	vector<future<int>>task;
	for(int i=1;i<num_threads;i++)task.push_back(async(launch::async,f,i));
	int r=f(0);
	for(auto &t:task)r=max(r,t.get());
	return r;
}

int main(){
	int m,n;
	scanf("%d%d",&m,&n);
	printf("%d\n",lightsout(m,n));
}

• やはり効率はOpenMPに比べると落ちるらしい。
• ただ、C++11標準なので、clangでも使えるのが良いですね。