LoginSignup
0
2

More than 5 years have passed since last update.

@cielavenir

十文字に反転して色を揃えて！(single/OpenMP)

Last updated at Posted at 2016-09-30
シリーズ：掃き出し法について 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

概要

  • m x nサイズのライツアウトがある時、(解ける盤面の中で)最短手数が最大となる盤面についてその手数を出力せよ。
  • ただし、全て色が付いている状態と全て消えている状態のどちらかに遷移できれば良いものとする。

解法

解答行列

まず、ライツアウトの解答行列を掃き出し法で求める。同時に0解(quiet pattern)を保持しておく。(m*n-(0解の個数)をkとする)

最短手数

ある盤面Xからの最短手数は、以下の手順で求められる。

  • Xのk-1ビットまでについて、真なら、解答行列のk-1番目を重ねあわせる。重なり合わさった結果をAとする。
    • (k番目からm*n-1番目のビットは、解けるかどうかにしか関係しないため、無視して良い)
  • 0解の組み合わせを全て列挙し(1<<(0解の個数)通り)、それぞれをAと重ねあわせる。
  • 立っているビットの数が最小の場合の「0解の組み合わせとAとの重ねあわせ」がその盤面の最適解であり、ビットの数が最短手数である。

盤面列挙

  • 以上の手順を、1<<k通りの盤面に対して行い、最短手数が最大となる盤面を探せば良い。
  • ただし、今回は、最終的な色がどちらでも良いので、XとX^MASKとのそれぞれに対し最短手数を計算し最小を取るようにする。

計算量

  • O(MN2 + K 2MN)となります。
    • KはM,Nによって変化するので、MxNの値が同じでも計算量が異なることがあります。
  • もう少し減らせる気がするので、少し残念ではあります。
  • m*nの上限は設問では18ですが、5x5でも、(後半戦はループ回数が23*2 * 2**25 = 16億回なので)1秒を切ることは可能です。
  • val_tをintに直せば、ideoneでも0.7秒で終わるようです。
    • まあそれも先日のバージョンアップでPyramidからCubeに切り替わったからだと思うので感謝。

感想

  • 今回、激むずでした…。シーズン2の中では1番難しいのではないでしょうか。
    • シーズン1の最速の連絡網には及びませんが…。
  • ライツアウトの解法については知っていましたが、最短手数の計算方法は詳しく知らなかったので、勉強になりました。

答案

  • C++の機能はvectorとswapしか使っていないので、気合があればCに直せると思います…。
tyama_codeiq2972_openmp.cpp
// single(tlstをメモ化する前の計測なので時間多めですが、大した差ではないはず)
// 5 5: 12 0.72s
// 3 9: 21 9.72s
// 5 6: 23 100.38s
// 4 8: 22 396.15s
// 6 6: 22 5996.84s

// openmp
// 5 5: 0.06s
// 3 9: 0.83s
// 5 6: 7.26s
// 4 8: 29.18s
// 6 6: 484.53s

#include <vector>
#include <algorithm>
#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 r=0;
    #pragma omp parallel for reduction(max:r)
    for(val_t i_=0;i_<(val_t)1<<k;i_++){
        //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;
}

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

最後に

  • 上限18なので、探索は考えませんでした。 16だったら考えたんですけどねぇ…。
  • まあ、6x6でも(2時間近くかかりますが)解けるので、いいんじゃないでしょうか(探索しようとすると メモリが550GB 必要です)。
  • 状態が変化しない点は、並列化が施せるのがうりでしょうか。スパコンでは、6x6でも10分以内で解くことができました。(尤も、自動採点だと並列化にならないのですが…。)

161212

元の説明をよく読んだら、ビット転置をしなくてもそのまま解答にできるんですね…。しかも吐き出しが途中で終わったときの取り回しが楽。

0
2
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
0
2