[1]はじめに

非負整数 \(X\) に対して \(X\ \mathrm{AND}\ Y=X\) を満たす非負整数 \(Y\) からなる集合を \(X\) の上位集合と言います。

[2]二分探索の利用

解を求めるには、\(0\) で初期化された変数 \(\mathrm{ANS}\) を持ち、以下の操作を \(i=31,30,\dots,1,0\) の順に行えばいいです。

• 選んだ $K$ 要素のビット単位 $\mathrm{AND}$ として $\mathrm{ANS}+2^i$ の上位集合の要素のいずれかを作るために必要な操作回数が $M$ 以下の場合、$\mathrm{ANS}$ を $\mathrm{ANS}+2^i$ にする。

この貪欲法の正当性の証明は \(2^i > 2^0 + 2^1 + \dots + 2^{i-1}\) であることよりできるだけ上位の bit を \(1\) にすることを優先すればよいことから導かれます。

[3]判定問題の解法

選んだ \(K\) 要素のビット単位 \(\mathrm{AND}\) として非負整数 \(X\) の上位集合の要素のいずれかを作るために必要な操作回数を求めます。

\(1 \le i \le N\) を満たす整数 \(i\) に対して \(A_i\) 以上かつ \(X\) の上位集合に含まれる最小の整数 \(B_i\) を求め、\(B_i - A_i\) が小さい方から \(K\) 個選べばよいです。

\(A_i\) 以上かつ \(X\) の上位集合に含まれる最小の整数 \(B_i\) の求め方は、以下の操作を \(j=31,30,\dots,1,0\) の順に行えばよいです。

• $X$ の $j$ bit 目が $1$ ならば、何も行わない。
• $X$ の $j$ bit 目が $0$ ならば、$X$ の $0$ bit 目から $j-1$ bit 目を全て $1$ にした値が $A_i$ 未満であれば $X$ の $j$ bit 目を $1$ にする。そうでないならば何もしない。

よって、選んだ \(K\) 要素のビット単位 \(\mathrm{AND}\) として非負整数 \(X\) の上位集合の要素のいずれかを作るために必要な操作回数を \(\mathrm{O}(N(\log N + \log A))\) で求めることができました。

[4]まとめ

よって、この問題を \(\mathrm{O}(N\log A(\log N + \log A))\) で解くことができます。

最大で \(A_i\) は \(2^{31} - 2\) になることに注意してください。