Integer Sequences (SEQUENCE)

keyword

グレイコード　C++

問題概要

整数N,a,b(N<15, a,b < 2^N)が与えられる。0~2^N-1を隣接する要素がハミング距離1になるように並び替えた解き、a,bが隣接(環状に考えて)しないようなものがあればそれを出力する問題。

解法

こういう数列にはグレイコードという名前が付いているらしい。調べるとa_i = i ^ (i>>1)で生成できるらしい。ちょっと考えるとN=1,2のときは解がないとわかる(もちろんa,bのハミング距離が1のとき)。それ以上のときは、「まあ適当に置換してやれば大丈夫だろう」と考える。つまり、2進表記で縦に並べたとき、i列目とj列目を入れ換えてやる。ただしこの方法だと、唯一N=3, a=2, b=3のときに解を出力しないので、その場合は自前で埋め込む。以下は向こうでテストできないので適当にテストケースを作って試すプログラム。

感想

こんな考え方じゃコンテスト中には解けないでしょう。

#include <cstdio>
#include <cstdlib>
using namespace std;

int tmp[1<<16];
int ans[1<<16];
int N, a, b;

void print(){
    if(0)for(int i=0; i<1<<N; i++)
        printf("%d%c",ans[i],i==(1<<N)-1?'\n':' ');
}

bool check(){
    for(int i=0; i<1<<N; i++)
        if(ans[i]==a && (ans[(i+1)%(1<<N)]==b || ans[(i+(1<<N)-1)%(1<<N)]==b))
            return false;
    print();
    return true;
}

void solve(){
    if(a>b){
        int t=a;
        a = b;
        b = t;
    }
    if(N==3 && a==2 && b==3){
        //puts("1 3 7 6 2 0 4 5");
        return ;
    }
    if(N<=2 && __builtin_popcount(a^b)==1){
        puts("-1");
        return ;
    }
    for(int i=0; i<1<<N; i++){
        ans[i] = tmp[i] = i ^ (i>>1);
    }
    if(check()) return ;
    for(int m=0; m<N; m++)if((1<<m) != (a^b)){
        int mask = (1<<m) | (a^b);
        for(int i=0; i<1<<N; i++)
            ans[i] = (tmp[i]&(~mask)) | 
                ( (((tmp[i]>>m)&1)?(a^b):0) | ((tmp[i]&(a^b))?1<<m:0) );
        if(check()) return ;
    }
    printf("%d %d %d ", N, a, b);
    puts("-1");
    return ;
}

int main(){
    int T;
    N = 15; a = 3; b = 2;
    solve();
    srandom(397511423);
    for(int t=0; t<1000000; t++){
        N = random()%12 + 3;
        a = random()%(1<<N);
        b = a ^ (1<<(random()%N));
        solve();
    }
    /*
    for(scanf("%d",&T);T--;){
        scanf("%d%d%d",&N,&a,&b);
        solve();
    }
    */
    return 0;
}