問題

問題概要

長さ $N$ の順列 $p,q$ がそれぞれあるかどうかを判定し、ある場合はその具体例を1つ示せ。

全ての $i = 1,2, \ldots , N$ について、 $p_i \neq i$ かつ $p_i \ AND \ i = 0$ であるような順列 $p$
全ての $i = 1,2, \ldots , N$ について、 $q_i \neq i$ かつ $q_i \ AND \ i \neq 0$ であるような順列 $q$

(ANDはbitwise and(C++でいう&演算子))

$1 \le N \le 10^5$

アイデア

pについて

まず、 $N$ が奇数の時は、このような $p$ は構成不可能であることが分かる。大前提としてbitwise andが0になるためには偶奇が異なっている必要があるが、奇数の方が個数が多いため必ず奇数同士のペアが発生し、そのペアのbitwise andは最下位ビットが必ず立つのでダメということになる。

残りは $N$ が偶数の時について考えることになるが、この時は必ず $p$ は存在する。その構築方法の1つを紹介する。

大事なことは、 $(2^k - i) AND (2^k +i-1) = 0$ になることに注目することである。これは、2の補数と正負の関係をイメージすると何となく分かる気がする。

(例: $k=5$ )

100000 = 2^5
011111 = 2^5 - 1

100001 = 2^5 + 1
011110 = 2^5 - 2

このような方法で、数が大きい方からペアを作っていけば良い。

qについて

まず、 $N$ が小さい部分について実験してみると $N \le 5$ については $q$ が存在しないことが分かる。

更に、 $N=6$ が構成可能であることはサンプルからも明らか(3 6 2 5 1 4)であり、 $N=7$ も構成可能であることが分かる(7 3 6 5 1 2 4)。

以降、 $N \ge 8$ について考えてみると、 $N$ がちょうど2の累乗の形になっている( $N = 2^m$ )ときには不可能である。これは、 $q_N$ に何を入れるかを考えてみると、 $2^m$ のビットが立っている数が他に存在しないので入れられるものが何もない。よって、不可能であると言える。

逆に、残りは全て可能であることが分かる。具体的な構成方法を考えると、まず、1~7の部分は上に書いたものと同じように埋めておき、8以降を最上位ビットごとにグループ化して、それをcyclic shiftしたものを並べていけば良い( $N$ が2の累乗じゃければ、グループが1つの要素になってしまうことがないのでOK)。

具体的には、

8 ~ 15 : 9 10 11 12 13 14 15 8
16 ~ 31 : 17 18 19 20 ... 30 31 16

のように埋めていけば良い。

実装(C++)

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define fi first
#define se second

void p(int n){
    if(n%2==1){
        cout << "NO" << endl;
        return;
    }

    vector<int> ans(n+1);

    int pw=1;
    while(pw*2<=n) pw*=2;

    while(pw>1){
        int i = 0;
        while(1){
            int idx = pw + i;
            int ridx = pw - i - 1;
            if(idx<=n && ridx>0 && ans[idx]==0 && ans[ridx]==0){
                ans[idx] = ridx;
                ans[ridx] = idx;
            }
            else break;
            ++i;
        }
        pw/=2;
    }

    cout << "YES" << endl;
    for(int i=1; i<=n; ++i) cout << ans[i] << " \n"[i==n];
}

void q(int n){
    bool ok = (n>=6);
    int pw = 2;
    while(pw<=n){
        if(pw == n) ok = false;
        pw *= 2;
    }
    if(!ok){
        cout << "NO" << endl;
        return;
    }

    vector<int> ans;
    if(n==6) ans = {0,3,6,2,5,1,4};
    else ans = {0,7,3,6,5,1,2,4};
    ans.resize(n+1);

    pw = 8;
    while(pw<n){
        for(int i=pw; i<min(pw*2-1,n); ++i) ans[i]=i+1;
        ans[min(pw*2-1,n)] = pw;
        pw *= 2;
    }

    cout << "YES" << endl;
    for(int i=1; i<=n; ++i) cout << ans[i] << " \n"[i==n];
}

int main(){
    int n;
    cin >>n;
    p(n);
    q(n);
    return 0;
}

裏紙

ほぼ競プロ、たまに日記

CF 909 F - AND-permutations

問題

問題概要

アイデア

pについて

qについて

実装(C++)