問題概要
長さ $N$ の $(0,1,\dots,N-1)$ の順列 $P$ (0-indexed) が存在し、隠されている。
$P$ の逆置換を $B$ とする。
以下の質問を高々 $2N$ 回使い、 $P$ を当てよ。
- $0 \le i,j < N$ なる整数 $i,j$ を指定し、 $P_i \oplus B_j$ を尋ねる。
但し、異なる $P$ 同士でどう質問しても区別がつかないケースがあるので、当てた順列と区別がつかない $P$ の個数も数え上げよ。
制約
・ $1 \le N \le 5000$
誤った初手1: $N$ が奇数の場合は $P_i,B_0$ の総 xor を取って $(0,1,\dots,N-1)$ の総 xor と xor すれば $B_0$ が分かって $P$ が復元できる
偶数の場合進みません。悲しい。
誤った初手2: $0$ の位置を当てに行く
実験の結果 $0$ の位置が異なるのに区別がつかないケースがあって上手く行かなそう。悲しい2。
誤った初手3: 順列の構造を考える
偶数長の環が特定できないのかな～と思ったらそういうわけでもなさそうだし binary trie の左右入れ替えみたいな操作が区別つかないのかなと思ったらそういうわけでもなさそうだし… 悲しい3。
正しい初手: $2N$ 個の質問でありうる $N^2$ 個の質問全てに答えられるようにする
$P_i \oplus B_j$ の任意の値を答えられるようにしたい。
とりあえず脳死で $P_0 \oplus B_j$ と $P_i \oplus B_0$ を全部訊くことにする。
直接答えを訊いてない部分では $(P_x \oplus B_y) \oplus (B_y \oplus P_z) \oplus (P_z \oplus B_w) = P_x \oplus B_w$ の形で、最低 $3$ 手かかりそう。
$P_0$ と $B_0$ をターミナルみたいなもんだと思うと以下の式が浮かんでくる。
$(P_i \oplus B_0) \oplus (B_0 \oplus P_0) \oplus (P_0 \oplus B_j) = P_i \oplus B_j$
これで、さっき脳死でした質問を使ってありうる質問全てに答えられることがわかった。
こうなればこっちのもん。制約 $N \le 5000$ より $P_0$ を $N$ 通り決め打って $P,B$ を復元して、
・$P$ が順列か否か
・$B$ が $P$ の逆順列になっているか
をチェックすればok。
Submission #207816383 - Codeforces
「ありうる質問全てに対する解答を復元しにかかる」という発想がキモかった。頭から抜け落ちてた。ただ「区別がつかない」ってそういうことなので「区別がつかない」が「ありうる質問全てに対する解答を復元しにかかる」という発想の枕詞なのかもしれない。
