ZONeエナジープログラミングコンテスト F-出会いと別れ
問題
$0$ から $2^n-1$ までの番号がついた星があります。
$i\oplus j$が $A_1, A_2, ..., A_M $のいずれにも含まれないような星 $i$と $j$を選んで、 相互に移動可能なワープホールを作ることができます。
$N-1$個のワープホールを作ることで、任意の2つの星の間をワープホールで移動できるようにしたいです。
この目標が可能であるか判定し、可能ならばワープホールの作り方の一例を示してください。
- $1\leq n\leq 18$
- $0<A_1 \lt A_2 \lt ... \lt A_M \lt N(=2^n)$
考察
方針
xor$(\oplus)$の出てくる問題なので, いくつかのパターンを最初に考えてみます。 具体的には、以下のようなものを考えます。
桁ごとに独立である性質を利用し、桁ごとに問題を分解する
計算順を問わない(交換則・結合則)。逆演算可能である。などの性質を利用する。
- 累積xor・いもす法・尺取法・セグメント木・クエリ平方分割・ポテンシャルなどに応用する。
xorが$0$になる場合の性質を利用する ($0$はxorの単位元)
- $A\oplus A=0$
- 全要素のxorが$0$である集合は、xorの値が等しい2つの集合に分割できる
xorの基底を使う(線形代数)
色々ありますが、今回は xorの基底を使う(線形代数) が一番可能性の高い切り口です。 (xor基底の説明は省きます 後で時間があったら書く)
理由ですが、問題の設定を基準にして以下のように考えられるためです。
まず、xorする対象が星の番号なので、星の番号に関するxorを考える。
ワープホールを通って移動する行為は、現在地$i$に整数$X$をxorする行為とみなせる。
このとき、整数$X$は特定の数でなければならない(具体的には、$A_1, ... , A_M$以外)
ある数に特定の数をxorする行為は、xor空間上で整数に基底を加える行為と等しい
なので、xor空間に当てはめて考えることで問題を整頓できる可能性が高い
以上から、xor基底を使って問題が解ける可能性が見えてきました。
他の方針についても考察しておきましょう。
桁ごとに独立である性質を利用し、桁ごとに問題を分解する
- 数列の問題などでは使えますが、星の番号を桁ごとに分解しても恩恵はなさそうです。
計算順を問わない、逆演算可能などの性質を利用する。
- 累積xorなどでデータの形を変えたい場合は有効ですが、そもそも構築問題なので変形したいようなデータがありません。必要が出てきたら改めて考える程度で良さそうです。
xorが$0$になる場合の性質を利用する
- それらしい要素が問題文にありません。星の番号のxorが0になるメリット等もなさそうです。
どの方針も最初の1手としてはあまり有効でなさそうなので、とりあえずxor基底を用いて解いてみるのが良さそうだと判断することができます。
xor基底を使う
- ワープホールを通って移動する行為は、現在地$i$に数$X$をxorするとみなせる。
ここで、$X$になる候補は$0$と$A_1, ... , A_M$ 以外です。($0$が除外されるのは、同じ星にワープしてしまうからです) これは通常の実装でも$O(N)$で求められるので問題ありません。
ワープホールは双方向に移動可能なので、任意の2つの星の間をワープホールを使って移動できる、というのは、星$0$から全ての星に移動できる、ということと同義です。
また、星$0$からある星にワープホールを複数回使って移動するという行為は、$0$に$X$候補を複数回xorする、と言い換えられます。
よって、任意の2つの星の間をワープホールを使って移動するためには、$0$に対して複数の$X$候補をxorすることで$0$以上$2^n-1$以下の任意の整数を作ることができればよいです。
ワープホールの個数に制限がないと仮定すると、線形基底の性質から、$n$個の独立したxor基底を$X$として使えば良いです。
理由は、$n$個の基底を$X_1, X_2, ... , X_n$とすると、
| $X_1$ | $X_2$ | $X_3$ | $X_4$ | ... | $X_n$ | 値 |
|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | ... | 0 | $0$ |
| 1 | 0 | 0 | 0 | ... | 0 | $X_1$ |
| 0 | 1 | 0 | 0 | ... | 0 | $X_2$ |
| 1 | 1 | 0 | 0 | ... | 0 | $X_1\oplus X_2$ |
| 0 | 0 | 1 | 0 | ... | 0 | $X_3$ |
| 1 | 0 | 1 | 0 | ... | 0 | $X_1\oplus X_3$ |
| 0 | 1 | 1 | 0 | ... | 0 | $X_2\oplus X_3$ |
| 1 | 1 | 1 | 0 | ... | 0 | $X_1\oplus X_2\oplus X_3$ |
| 0 | 0 | 0 | 1 | ... | 0 | $X_4$ |
| : | : | : | : | : | : | : |
| 1 | 1 | 1 | 1 | ... | 1 | $X_1\oplus X_2 \oplus ... \oplus X_n$ |
というように、n個ある基底を加える/加えないの2通りのn乗から、$0$以上$2^n-1$以下の全ての整数を作れるからです。
これらの$2^n$個の数が互いに異なることは、基底$X_1, X_2, ... , X_n$が互いに独立である、すなわち1個以上の異なる基底のxorをとっても$0$にならないことから証明できます。
作成される数は必ず$0$以上$2^n-1$になるので、$X$の選び方によらず、上記の表の「値」の列には$0$以上$2^n-1$以下の全ての整数が1回ずつ出現します。
このとき、例えば星$X_2\oplus X_3$と星$X_2\oplus X_3\oplus X_5$のxorは$X_5$なので、互いに直接ワープ可能です。
これを踏まえ、星$0$からある星、例えば星$X_2\oplus X_3\oplus X_5$に移動する場合、
$0\rightarrow X_2 \rightarrow X_2\oplus X_3 \rightarrow X_2\oplus X_3\oplus X_5$
というように番号順に辿っていくことで、星$0$から全ての星にワープできるようになります。
このとき移動先の星から移動元の星が一意に決まるので、ワープが星$0$以外の全ての星と1対1対応し、必要なワープの数が$N-1$個(問題文の条件を満たす)になります。
この移動を表にすると以下のようになります。
| 頂点($0$から辿るときの移動元) | 頂点(移動先) |
|---|---|
| $0$ | $X_1$ |
| $0$ | $X_2$ |
| $X_1$ | $X_1\oplus X_2$ |
| $0$ | $X_3$ |
| $X_1$ | $X_1\oplus X_3$ |
| $X_2$ | $X_2\oplus X_3$ |
| $X_1\oplus X_2$ | $X_1\oplus X_2\oplus X_3$ |
| : | : |
| $X_1\oplus X_2 \oplus ... \oplus X_{n-1}$ | $X_1\oplus X_2 \oplus ... \oplus X_{n-1} \oplus X_n$ |
以上の議論から、X候補からxor基底をn個選び出すことが可能であれば、$N-1$個のワープで任意の2星間の移動が可能になることが分かりました。
xor基底を取れない場合
逆に、X候補からxor基底をn個選べない場合を考えます。
例えば、$N=8$で$A={1,2,3,4,5,6,7}$の場合、$X$候補が存在しないので明らかに選べません。
ほかにも、$N=8$で$A={2,3,4,5}$の場合、$X$候補は${1,6,7}$となりますが、bit空間の自由度が$2$なのでxor基底は2つまでしか選べません(例: {1,6})。
このような場合、星$0$から移動できるのは$X$候補の部分空間のみなので、明らかに一部の星には移動することができません。
よって、 X候補からxor基底をn個選べない場合はどのようにワープを設置しても条件を満たせないことが分かりました。
xor基底の計算法
掃き出し法を使うのがスタンダードです。
X候補は最大で$N-1$個存在しますが、基底の数はxor空間の性質上高々$n$個にしかならないので制約の範囲内で計算できます。
(具体的な方法については後で加筆します)
実装
入力$A$から、$X$としてありうる数を列挙する。$(O(N))$
$X$から$n$個のxor基底を掃き出し法で選ぶ$(O(Nlog(N)))$
基底が$n$個未満なら不可能なので、$-1$を出力して終了。
基底が$n$個あるとき、上記の表を計算して出力する。$(O(N))$
