ぐろふぉのボス問自力討伐は流石にめちゃくちゃ嬉しいぜ、奥さん…
問題概要
以下のように生成されたサイズ $n$ の整数集合 $A$ がある。
$1$ 以上 $c$ 以下の全ての整数 $x$ について、 $x$ を確率 $0.5$ で含む。この決定はそれぞれの $x$ に対して独立に行われる。
以上の方法でランダムに生成された $A$ を、以下のクエリを高々 $\lceil 0.65 \times c \rceil$ 回使って特定せよ。なお、質問は全て一括で行う必要がある。
[? $x$] ... $A$ に含まれ、かつ $\gcd(x,y)=1$ を満たす整数 $y$ 全ての総XORを答える。
$100 \le c \le 10^6$
Step 1. 正しい質問をする
最初の観察として、例えば、 [? 6] == [? 12] は必ず成立します。なぜでしょうか?
実は、どのような整数 $z$ に対しても、 $\gcd(6,z)=1 \iff \gcd(12,z)=1$ なのです。
この理由は、 $6$ と $12$ に含まれる素因数の集合が等しいからです。
ということは、全ての Square-freeな整数(どのような $2$ 以上の平方数でも割り切れない整数) $w$ に対してのみ、 [? $w$] を質問すれば、質問によって得られうる全ての情報が手に入ります。
では、 Square-free な整数の割合は最大でどのくらいの値をとるでしょうか?
これに関しては実験するしかありません。 $c=115$ のときワーストとなりますが、この時でも $0.635 \times c$ 程度で収まるようです。なので、この質問は質問数の条件をクリアします。
Step 2. 情報を使いやすいように変形する
このパートでは、方針を先に決めてしまうと見通しがよくなります。以下を求めることをゴールとしてみましょう。
$P$ は何らかの素数の集合であるとする。(当たり前だが、 $P$ の要素の総積は必ず Square-free な整数となる。)
$f(P)=$ ( $A$ に含まれており、かつ含まれる素因数の集合が $P$ と完全に一致するような全ての整数の総 XOR) を求めたい。
ちなみに、これは条件は or より and で結ばれていた方がのちのち有利に働くということを見越しての方針立てです。
表記の簡単ため、 $q(P)=$ [? $P$ の総積] と表記します。なお、これ以降の説明では Square-free な整数 $x$ と何らかの素因数の集合 $X$ とを同一視しています。さらに、 $1$ と素因数の空集合とを同一視します。
まず、 $q(P) \oplus q(1) = $ ( $A$ に含まれており、かつ素因数として $P$ に含まれるものどれかを含む整数の総 XOR ) が成り立ちます。以降、 $q'(P)=q(P) \oplus q(1)$ とします。
スモールステップとして、 $r(P)=$ ( $A$ に含まれており、かつ素因数として $P$ に含まれるもの全てを含む整数の総 XOR ) を求めましょう。
実は、 $r(P)=$ (全ての空でない $P$ の部分集合 $Q$ について、 $q'(Q)$ の総XOR) が成立します。結論だけ聞いても途方に暮れそうですが、手で実験してみるとより理解が深まると思います。(端的にうれしさだけ説明すると、これにより、欲しいものが奇数回足され、いらないものが偶数回足されるようになります)
ただ、 $r(P)$ に対しては $P$ に含まれない素数についてなにひとつ制約がかかっていないので、余分な素因数をカットする感じで $f(P)$ を求めていきましょう。
実は、以下のアルゴリズムで、最終的に正しい $f(P)$ を求めることができます。
1. 最初は全ての素因数の集合 $P$ に対して $f(P)=r(P)$ とする。
2. $P$ の値が大きい方から順に、以下を行う。
2-1. $f(P)$ を現在の値で確定させる。
2-2. 全ての $P$ の部分集合 $Q$ (空集合も含む)に対して、 $f(Q) \leftarrow f(Q) \oplus f(P)$ と更新する。 ($f(Q)$ から $f(P)$ の影響を排除するイメージ)
こちらも実験をしてみることで理解が深まると思います。特に、暗黙のうちに、 $P$ が十分 $c$ に近い時は $r(P)=f(P)$ が成り立つという事実を利用しています。
この $2$ 回の操作は、素因数によるゼータ変換やメビウス変換とお気持ちが近いです。この記事が参考資料です。
エラトステネスの篩の活用法を総特集！ 〜 高速素因数分解・メビウスの反転公式 〜 - Qiita
Step 3. 答えを求める
いよいよ大詰め、求解パートです。
今後の説明が楽なので、いったん $c=10^6$ としてみましょう。
Step 2. により、 $f(P)=$ ( $A$ に含まれており、かつ含まれる素因数の集合が $P$ と完全に一致するような全ての整数の総 XOR) が求まりました。
では、この総 XOR からもとの整数を復元することを考えてみましょう。
方法はいくつかありますが、一番最初に思い浮かぶのは bit 全探索 です。
ここで気になるのは「含まれる素因数の集合が $P$ と完全に一致する」という条件を満たす整数の数の最大値です。これも実験すると求まるのですが、 $c=10^6$ の場合で $200$ を超えてしまいます。よって、 bit 全探索は無謀であることが分かりました。
よくよく考えてみれば、総 XOR の情報量は高々 20bit です。その程度の情報量で 200bit を区別できるはずがありません。ここで、あることに気づきます。
「実は、条件を満たす整数の集合はけっこうたくさん考えられるのでは?」
その疑念が、問題文の以下の文章によって確信へと変わります。
全てのありうる入力に対して同じ振る舞いをする整数の集合が複数考えられる場合は、どれを求めてもよい。
結局、現在解くべき問題は以下です。
何らかの整数の集合 $S$ が与えられるので、総 XOR が $x$ となるような部分集合を求めよ。ただし、そのようなものがたくさんある場合はサイズが $|S|/2$ 程度のものを選ぶとちょうどよい。(即ち、多少サイズの融通が利くということ)
この問題を解くにあたって、「含まれる整数を特定する≒bit行列上で一次方程式を解く」 という事実から、あるアルゴリズムが想起されます。
ずばり、そのアルゴリズムとは「(XOR)掃き出し法」です。
今度は、 $S$ に入っている整数を bit ベクトルとして扱います。
このとき、「一次独立なベクトル」と「一次従属なベクトル」にあらかじめ仕分けておきます(うまいことやって前者をランダムに選べるとよいです)。こうすることによって、「一次従属なベクトル」で大まかにサイズを決定し、「一次独立なベクトル」で総XORの値を調整するという芸当が可能になります。
ここでおおよそこの問題を解くことができたかに見えますが、まだ完全に解け切っていない課題があります。その課題とは、「最終的なサイズを $n$ とする」必要があることです。(ヒントに見えたサイズ $n$ という条件が、最後に残った難題として降りかかってくるの、エモみがありませんか…?)
しかし、この難題は以下のような方針でおおよそ解決します。(この方針の下では悪意のあるケースで解けないので、ここでランダム性を利用します)
サイズの小さい問題から「入れる/入れない」を決定していくことを考える。
現在までに入れる / 入れないが決まった整数を $K$ 個とすると、追加された整数は $K \times \frac{n}{c}$ 個程度だと望ましい。うまく「一次従属なベクトルの本数」を決めることによって、このペースとの誤差はおよそ「一次独立なベクトルの本数の半分」以内くらいに収まる感じで進んでいく。
最後の問題だけは、一次従属なベクトルの本数に少しランダムな揺らぎをもたせて、帳尻が合う解を見つける。
(この部分は著しく厳密性を欠く説明ですみません…)
以上より、この問題を解くことが出来ました。ちなみに $c$ が小さい場合はけっこう危ない気がしていましたが、完成したコードをもとに手元でいろいろ実験してみたところ、けっこうちゃんと解けるようです($c=100$ でも一次従属のベクトルが多少出る & ある程度の集合について、答えが一意に定まるため?)。
かなり端折って説明しているので、詳細はコードを見てください。他にも息をするように使う文字を間違えていると思うので、怪しいと思った点もコードを参照してください。
