問題

長さ $n$ の整数列 $a$ と正の整数 $k$ が与えられる。この数列 $a$ に対して、ある要素を $1$ だけ増やすという作業を最大 $k$ 回行うことができる。

作業終了後に、 $a$ の各要素の bitwise AND を取ったときの最大値を求めよ。

ただし、 $k$ の値は全部で $q$ 個与えられるので、その $q$ 個の場合についての最大値をそれぞれ求めよ。

入力

最初の1行目には、整数 $n, q$ が与えられる。

次の1行には、整数 ${a}_{i}$ （ただし、 $1 \leq i \leq n$ ）が順番に与えられる。

その後 $q$ 行にわたり、 $i$ 行目には整数 ${k}_{i}$ が順に与えられる。（ただし、 $1 \leq i \leq q$ ）

条件

$1 \leq n, q \leq {10}^{5}$
$1 \leq n \cdot q \leq {10}^{5}$
$0 \leq {a}_{i} \leq {10}^{6}$
$0 \leq {k}_{i} \leq {10}^{18}$

出力

$q$ 行にわたり、 $i$ 行目には $k = {k}_{i}$ のときの最大値を出力すること。

解法

この問題は2進数で表したときのANDの値を最大化する問題なので、2進数で表したときの桁数の大きい方から、ANDの値を1にできるかを考えます。

ここで、「数列 $a$ のすべての値に対してANDを取った値が ${2}^{j}$ の桁で $1$ になる」という状況を作るには、どのようにすればよいのかということを考えます。すなわち、 \begin{align} ({a}_{1} \ \& \ {a}_{2} \ \& \ \cdots \ \& \ {a}_{n}) \ \& \ {2}^{j} = {2}^{j} \end{align} となるようにするために、 ${a}_{i}$ のそれぞれに $1$ を加える回数について考えます。

整数 ${2}^{j}$ は2進数で表したときに $1$ がどこか1つの桁にのみ出てくる整数であるので、 ${a}_{i} \ \mathrm{AND} \ {2}^{j}$ の値は $0$ または ${2}^{j}$ となります。従って、

${a}_{i} \ \mathrm{AND} \ {2}^{j} = 0$ のとき: ${2}^{j} - ({a}_{i} \% {2}^{j})$ を ${a}_{i}$ に加えることにより、 ${a}_{i} \ \mathrm{AND} \ {2}^{j} = {2}^{j}$ にできる
${a}_{i} \ \mathrm{AND} \ {2}^{j} = {2}^{j}$ のとき: ${a}_{i}$ に何も行わなくても、 ${a}_{i} \ \mathrm{AND} \ {2}^{j} = {2}^{j}$ が成立する

ということがそれぞれ言えるので、 ${a}_{i} \ \mathrm{AND} \ {2}^{j} = 0$ であるすべての整数 $i$ に対して加えた値の総和が $k$ 以下であれば、最終的な値を ${2}^{j}$ にできると言えます。

このことから、 $j$ が大きい方から順に上記の作業を行い、 ${a}_{i}$ に対して足した値の合計が $k$ 以下になるようにしたときの最終的な値が答えとなります。

ここで、 $k \leq {10}^{18}$ であり、 ${10}^{18} \lt {2}^{60}$ であるので、 $j = 60, 59, \cdots, 1, 0$ に対して行うことにより答えが得られます。

また、各 $k$ に対して合計 $61n$ 回の計算を行い、 $k$ の値は $q$ 個分与えられるので、この方法では $O(nq)$ の計算量で求められます。この問題では $nq \leq {10}^{5}$ であるので、実行時間制限にも十分間に合うと言えます。

ソースコード

整数列 $a$ と整数 $n, k$ が与えられている状態で、最大値を返す関数 solve() を以下のように実装しました。

int n, q;
ll a[int(1e5 + 5)], b[int(1e5 + 5)]; // b[i] は solve() の中で a[i] の値を一時的に保存するための配列
ll k;

ll solve() {
  // 一次保存用の配列 b に配列 a の値をコピーする
  for (int i = 1; i <= n; i++) {
    b[i] = a[i];
  }

  ll digit = pow(2, 60), cnt = 0, ans = 0; // digit は 2 ^ j の値を、cnt は現在までに1が足された回数を、ans は最終的な最大値をそれぞれ表す

  // digit の値が 0 より大きい間は以下のループを回す
  while (digit > 0) {
    ll now_cnt = 0; // now_cnt は現在の digit の値にするために必要な計算回数を表す
    for (int i = 1; i <= n; i++) {
      if ((b[i] & digit) > 0) {
        continue; // b[i] が digit の桁を含んでいれば、値を足す必要はない
      }
      now_cnt += digit - (b[i] % digit); // digit の桁を含んでいないときは、上記の数だけ足す必要がある
      if (now_cnt > k) {
        break; // そもそも、now_cnt が k を超えたら digit の値にはできないのでループから抜ける（オーバーフロー対策）
      }
    }

    if (now_cnt + cnt <= k) { // もし now_cnt と cnt の和が k 以下であれば、digit を答えに足すことができる
      cnt += now_cnt; // cnt の値の更新
      ans += digit; // ans の値の更新
      for (int i = 1; i <= n; i++) {
        if ((b[i] & digit) == 0) {
          b[i] += digit - (b[i] % digit); // b[i] の値の更新
        }
      }
    }
    digit /= 2; // 次の桁を見るため、digit 自身を 2 で割る
  }

  return ans;
}