概要

\(N\) ビットのランプ列に対して最大 \(K\) 回の操作（左端の 0 を除去して右端に 1 を追加）を行った後、\(M+1\) 個のランプ列すべてに共通の分割位置 \(p\) を選び、左右部分の整数値の総和 \(A + B\) を最大化する問題です。

考察

操作の本質を理解する

左端のランプは最下位ビット（LSB）に対応します。操作は「LSB が 0 なら除去して、最上位側に 1 を追加する」ことです。

これはビット演算で言えば： $\(X \leftarrow (X \gg 1) \mid (1 \ll (N-1))\)$

つまり、\(X\) の末尾の連続する 0 を 1 つずつ削りながら、上位に 1 を詰めていく操作です。

操作回数の決定

\(X\) の下位に連続する 0 の個数を \(t\) とすると（\(X = 0\) なら \(t = N\)）、操作は \(t\) 回目で左端が 1 になり停止します。よって実際に行われる操作回数は \(\text{ops} = \min(t, K)\) です。

操作後の値

\(\text{ops}\) 回操作した後の値は： $\(X_{\text{final}} = (X \gg \text{ops}) \mid (((1 \ll \text{ops}) - 1) \ll (N - \text{ops}))\)$

下位 \(\text{ops}\) ビット（すべて 0）を除去して右シフトし、上位 \(\text{ops}\) ビットを 1 で埋めた形です。

分割位置の選択

分割位置 \(p\) でランプ列 \(Z\) を分割すると： - 左側部分の値：\(Z \mathbin{\&} (2^p - 1)\)（下位 \(p\) ビット） - 右側部分の値：\(Z \gg p\)（上位 \(N-p\) ビット）

右側部分は \(2^0\) から数え直すため、単純に右シフトした値になります。

全 \(M+1\) 個のランプ列について左右の値をそれぞれ足し合わせ、その合計が最大となる \(p\) を探します。

アルゴリズム

1. \(X\) の末尾の連続する 0 の個数 \(t\) を求め、\(\text{ops} = \min(t, K)\) を計算する
2. \(X_{\text{final}}\) を上記の式で計算する
3. 各分割位置 \(p\)（\(1 \le p \le N-1\)）について：
   • \(X_{\text{final}}\) と全 \(Y_j\) の左右部分の値の総和を計算する
4. 全ての \(p\) に対する総和の最大値を出力する

具体例（\(N=4, X=12\) すなわちビット列 0011）： - 左端（LSB）は 0 なので操作実行：右シフト＋上位に1 → 1011（末尾0が2個なので最大2回操作） - \(p=2\) で分割すると左 10（値2）、右 11（値3）→ 合計5

計算量

• 時間計算量: \(O(N \cdot M)\)（\(N-1\) 通りの分割位置 × \(M+1\) 個のランプ列）
• 空間計算量: \(O(M)\)（入力の \(Y\) 配列の保持）

\(N \le 46\), \(M \le 2 \times 10^5\) より、約 \(9 \times 10^6\) 回の演算で十分高速です。

実装のポイント

• __builtin_ctzll で末尾の 0 の個数を高速に取得できるが、\(X = 0\) の場合は未定義動作になるため、別途 \(t = N\) と処理する

• \(\text{ops} = N\) の場合（全ビット 0 で \(K \ge N\)）、\(X_{\text{final}} = 2^N - 1\)（全ビット 1）となる特殊ケースに注意

• \(N \le 46\) なので long long（64ビット整数）で全てのビット演算が収まる

• 答えが signed 64-bit integer に収まることが保証されているため、オーバーフローの心配は不要

  ソースコード

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    long long N, K, M, X;
    cin >> N >> K >> M >> X;
    
    vector<long long> Y(M);
    for (int i = 0; i < M; i++) cin >> Y[i];
    
    // Compute trailing zeros of X (as N-bit number)
    int t;
    if (X == 0) {
        t = N;
    } else {
        t = __builtin_ctzll(X);
    }
    
    long long ops = min((long long)t, K);
    long long X_final;
    if (ops == N) {
        X_final = (1LL << N) - 1;
    } else {
        X_final = (X >> ops) | (((1LL << ops) - 1) << (N - ops));
    }
    
    long long ans = 0;
    for (int p = 1; p < N; p++) {
        long long mask = (1LL << p) - 1;
        long long total = (X_final & mask) + (X_final >> p);
        for (int j = 0; j < M; j++) {
            total += (Y[j] & mask) + (Y[j] >> p);
        }
        ans = max(ans, total);
    }
    
    cout << ans << endl;
    return 0;
}

---

この解説は claude4.6opus-thinking によって生成されました。