概要

高橋君の列 \(X\) を「左端が 0 の間だけ最大 \(K\) 回」更新したあと、全列（高橋君 1 本 + 青木君 \(M\) 本）に共通の分割位置 \(p\) を選び、左部分の値の総和 \(A\) と右部分の値の総和 \(B\) の合計 \(A+B\) を最大化する問題です。
ポイントは、各ビット位置で 1 が何本あるかに注目すると、各 \(p\) の評価を高速にできることです。

考察

まず高橋君の操作を整理します。
左端（この問題では最下位ビット）を見て、

• 1 なら即終了
• 0 ならそのビットを捨てて右端に 1 を足す

なので、整数で書くと 1 回の操作は - 右シフト >> 1 - 最上位ビット（\(N-1\) ビット目）を 1 にする

です。
つまりコードの tx = (tx >> 1) | (1ULL << (N-1)) と同じです。これを「\(K\) 回まで」かつ「LSB が 0 の間」だけ回せばよいです。

---

次に分割後スコアです。分割位置を \(p\) とすると、各列の

• 左部分は元のビット \(0..p-1\) をそのまま重み \(2^0..2^{p-1}\) で評価
• 右部分は元のビット \(p..N-1\) を詰め直して重み \(2^0..2^{N-p-1}\) で評価

されます。

ここで重要なのは、列ごとに見るのではなく
「ビット \(b\) が 1 の列数」を bitCount[b] として集計することです。
すると

\[ A = \sum_{b=0}^{p-1} \text{bitCount}[b]\cdot 2^b \]

\[ B = \sum_{b=p}^{N-1} \text{bitCount}[b]\cdot 2^{b-p} \]

となり、\(A+B\) は bitCount だけで計算できます。

---

素朴に各 \(p\) ごとに上式を最初から計算すると \(O(N^2)\)（各 \(p\) で全ビット走査）です。
\(N\le 46\) なので一見間に合いますが、より整理された実装としては境界を 1 つずつ動かす更新が自然です。

• leftVal = 現在の \(A\)
• rightVal = 現在の \(B\)

として、\(p-1 \to p\) へ進めるとき

1. 左に新しくビット \(p-1\) が入る
   \(\Rightarrow\) leftVal += bitCount[p-1] * 2^{p-1}

2. 右は「先頭項 bitCount[p-1] を除いて全体を 1bit 右に詰める」
   \(\Rightarrow\) rightVal = (rightVal - bitCount[p-1]) / 2

で更新できます。これで全 \(p\) を \(O(N)\) で走査できます。

アルゴリズム

1. 入力を読む。
2. 高橋君の列 tx を操作ルールに従ってシミュレーションする。
   while (t < K && (tx&1)==0) tx = (tx>>1) | (1<<(N-1))
3. bitCount[b]（\(0\le b <N\)）を作る。
   
   • tx の各ビット
   • 全ての Y_j の各ビット
     を合算する。
4. 2 の冪 pw[i]=2^i を前計算。
5. まず \(p=1\) のときの
   • leftVal = bitCount[0]
   • rightVal = sum_{b=1}^{N-1} bitCount[b]*2^{b-1} を計算し、ans を更新。
6. \(p=2..N-1\) について順に
   • leftVal += bitCount[p-1]*2^{p-1}
   • rightVal = (rightVal - bitCount[p-1]) / 2
   • ans = max(ans, leftVal + rightVal)
7. ans を出力。

計算量

• 時間計算量: \(O(NM + N + \min(K,N))\)（実質 \(O(NM)\)）
• 空間計算量: \(O(N + M)\)（Y を保持する実装）

実装のポイント

• ビット操作のため unsigned long long を使う（\(N\le 46\) なので安全）。

• 答えや総和は long long で管理（問題文で 64-bit に収まる保証あり）。

• M=0 のとき 2 行目が無い入力形式でも、このコードは for ループが 0 回で自然に対応可能。

• 更新式 rightVal = (rightVal - bitCount[p-1]) / 2 は、数式変形に基づく整数演算で必ず割り切れます。

  ソースコード

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M;
    long long K;
    unsigned long long X;
    cin >> N >> K >> M >> X;

    vector<unsigned long long> Y(M);
    for (int i = 0; i < M; i++) cin >> Y[i];

    // Simulate Takahashi's process on X:
    // while LSB is 0 and operations < K:
    //   X = (X >> 1) + (1ULL << (N-1))
    unsigned long long tx = X;
    long long t = 0;
    while (t < K && ((tx & 1ULL) == 0ULL)) {
        tx >>= 1;
        tx |= (1ULL << (N - 1));
        t++;
    }

    // bitCount[b] = number of sequences (tx + all Y) whose bit b is 1, 0-based from left(LSB side)
    vector<long long> bitCount(N, 0);
    for (int b = 0; b < N; b++) {
        if ((tx >> b) & 1ULL) bitCount[b]++;
    }
    for (auto v : Y) {
        for (int b = 0; b < N; b++) {
            if ((v >> b) & 1ULL) bitCount[b]++;
        }
    }

    // For split p (1..N-1):
    // A = sum_{b=0..p-1} bitCount[b] * 2^b
    // B = sum_{b=p..N-1} bitCount[b] * 2^(b-p)
    // maximize A+B
    long long ans = LLONG_MIN;

    // Precompute powers of two up to N
    vector<long long> pw(N + 1, 1);
    for (int i = 1; i <= N; i++) pw[i] = pw[i - 1] << 1;

    // Compute initial for p=1
    // leftVal = A for current p
    // rightVal = B for current p
    long long leftVal = bitCount[0] * pw[0];
    long long rightVal = 0;
    for (int b = 1; b < N; b++) {
        rightVal += bitCount[b] * pw[b - 1];
    }
    ans = max(ans, leftVal + rightVal);

    for (int p = 2; p <= N - 1; p++) {
        // Move boundary from p-1 to p:
        // New left adds bit p-1 with weight 2^(p-1)
        leftVal += bitCount[p - 1] * pw[p - 1];

        // right part indices shift:
        // old right had sum_{b=p-1..N-1} bitCount[b]*2^(b-(p-1))
        // new right is sum_{b=p..N-1} bitCount[b]*2^(b-p)
        // => newRight = (oldRight - bitCount[p-1]) / 2
        rightVal = (rightVal - bitCount[p - 1]) / 2;

        ans = max(ans, leftVal + rightVal);
    }

    cout << ans << '\n';
    return 0;
}

---

この解説は gpt-5.3-codex によって生成されました。