問題概要
整数 $N$ が与えられるので、以下の条件を満たす $(1,2,\dots,N)$ の順列 $P$ があるかどうかそれぞれ判定し、あれば $1$ つ構築してください。
A. 全ての整数 $1 \le i \le N$ について、 $P_i \neq i$ かつ $(P_i \& i) = 0$ を満たす。
B. 全ての整数 $1 \le i \le N$ について、 $P_i \neq i$ かつ $(P_i \& i) \neq 0$ を満たす。
但し $\&$ で bitwise-and を表す。
$1 \le N \le 10^5$
まずは、実験データを見てみましょう。
n = 1:
A.
B.n = 2:
A. 2 1
B.n = 3:
A.
B.n = 4:
A. 2 1 4 3
B.n = 5:
A.
B.n = 6:
A. 6 5 4 3 2 1
B. 3 6 1 5 4 2n = 7:
A.
B. 3 6 1 5 4 7 2n = 8:
A. 6 5 4 3 2 1 8 7
B.n = 9:
A.
B. 3 6 1 5 4 7 2 9 8n = 10:
A. 2 1 4 3 10 9 8 7 6 5
B. 3 6 1 5 4 2 9 10 7 8n = 11:
A.
B. 3 6 1 5 4 2 9 10 7 11 8n = 12:
A. 2 1 12 11 10 9 8 7 6 5 4 3
B. 3 6 1 5 4 2 9 10 7 8 12 11
(ただし、各解は辞書順最小のものである)
ここから解法を導出していきましょう。
- 「A. の順列が存在する」 $\Leftrightarrow$ 「 $N$ が偶数」
- 「B. の順列が存在する」 $\Leftrightarrow$ 「 $N \ge 6$ かつ $N$ が $2$ 冪でない」
という予想が立てられます。
これは実際正しいので、証明しながら解いていきましょう。
$N$ が奇数である場合に A. の順列が存在しないことの証明
$1,2,\dots,N$ のうち最下位 bit が立っているものが過半数なので、必ず $(P_i \& i)$ のうち少なくとも $1$ つに最下位 bit が立っている。
$N$ が $2$ 冪である場合に B. の順列が存在しないことの証明
$N$ は最上位 bit しか立っていないが、整数 $1 \le i \le N$ を使って $(N \& i) \neq 0$ とするためには $i = N$ とするしかないが、これは $P_i \neq i$ の条件に反する。
これで、存在しないならその理由がある程度分かりました。なので残りをあると仮定して構成しにかかります。
A. について:
$N$ が $2$ 冪の時を考えましょう。このとき $N$ の最上位 bit はどうでもよいことに注意してください。( $N$ 以外に最上位 bit が立っている数はないので)
すると、 $N=8$ の場合以下のようにマッチング (左辺 $u$ 、右辺 $v$ とするとき $P_u=v,P_v=u$ とする) すればよいことがわかります。
(2進法で)
(1)000 - 111
001 - 110
010 - 101
011 - 100
(10進法で)
8 - 7
1 - 6
2 - 5
3 - 4
では、 $N$ が $2$ 冪ではない偶数であった場合にどのようにすればよいでしょうか。
実は、以下の手順で構成可能です。
- まず、 $N$ が $2$ 冪であった時と同じようなマッチングを考え、そこでマッチングできる相手がいるならする。このときの bit 数を $k$ bit とする。
- この上で、マッチングできずに残った整数はある偶数 $r$ を用いて区間 $[1,r]$ 内の全ての整数であることが言える。
- さらに、マッチングできずに残った整数の先頭 bit は必ず $0$ である。(もし $1$ ならばマッチング相手がいるはずである)
- よって、残った整数を $k - 1$ bit であると見做して再帰的に繰り返す。
- $k=2$ でのマッチングを終えた時点でマッチング相手が見つからないということはない。
よって、 $N$ が偶数であった場合に A. の順列は構成できました。
B. について:
$N = 6,7$ の場合は実験で発見した解を使う。
$N>8$ かつ $N$ が $2$ 冪でない場合は以下のように構成できます。
実験で見つけた $N=7$ の解である $(3,6,1,5,4,7,2)$ の後ろに以下を順にくっつける。
$i=3,4,\dots$ に対して、 $l=2^i,r=\min(2^{i+1}-1,N)$ について、 $l < r$ (等号は入りえないことに注意) であれば $(l+1,l+2,\dots,r,l)$ を順にくっつける。
(これにより、 $2^i$ の位の bitwise-and を必ず $1$ にできる)
よって、 $N>8$ かつ $N$ が $2$ 冪でない場合に B. の順列は構成できました。
Submission #169517110 - Codeforces
問題自体はちょっと昔だが、最近の 600-700 点問題の傾向に近いという印象。
