| シリーズ：掃き出し法について | 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でも使えるのが良いですね。