概要

高橋君のランプ列 \(X\) に対して条件に基づいたビットシフト操作を最大 \(K\) 回行った後、\(M\) 個のランプ列 \(Y_j\) と合わせた計 \(M+1\) 本の列を共通の地点 \(p\) で分割します。分割された左側と右側の値を全列で合計したとき、その総和 \(A+B\) を最大化する問題です。

考察

1. 高橋君の操作のシミュレーション

高橋君の操作は、「左端が \(0\) である限り、それを取り除いて右端に \(1\) を追加する」というものです。これはビット表現で見ると以下のようになります。 - 左端（最下位ビット）が \(0\) なら、全体を右に \(1\) ビットシフトし、最上位ビット（\(2^{N-1}\) の位）を \(1\) にする。 - この操作を「\(K\) 回行う」か「最下位ビットが \(1\) になる」まで繰り返す。

つまり、初期状態 \(X\) の下位ビットに並んでいる連続した \(0\) の個数を \(z\) とすると、実際の操作回数 \(k\) は \(\min(K, z)\) となります。 操作後の \(X\) は、元の値を \(k\) ビット右シフトし、空いた上位 \(k\) ビットをすべて \(1\) で埋めたものになります。

2. スコアの計算式の整理

分割位置を \(p\) (\(1 \le p \le N-1\)) としたとき、あるランプ列 \(S\) のスコアは以下の和です。 - 左側部分の整数値: \(S\) の下位 \(p\) ビットが表す値。 - 右側部分の整数値: \(S\) の上位 \(N-p\) ビットを、改めて \(2^0\) から数え直した値（右に \(p\) ビットシフトした値）。

\(M+1\) 個の全ランプ列について、各ビット位置 \(i\) (\(0 \le i < N\)) に立っている \(1\) の総数を \(count[i]\) とします。すると、全ランプ列の左側の総和 \(A\) と右側の総和 \(B\) は次のように表せます。 $\(A = \sum_{i=0}^{p-1} count[i] \cdot 2^i\)\( \)\(B = \sum_{i=p}^{N-1} count[i] \cdot 2^{i-p}\)$

3. 効率的な最大値の探索

分割位置 \(p\) は \(1\) から \(N-1\) まで変化します。各 \(p\) に対して愚直に \(A\) と \(B\) を計算すると \(O(N^2)\) かかりますが、以下のように累積和的な考え方を用いることで \(O(N)\) で計算可能です。 - \(A\) は \(p\) を増やすごとに \(count[p-1] \cdot 2^{p-1}\) を足していくことで更新できます。 - \(B\) は \(p\) を減らす方向に計算すると \(B(p) = count[p] + 2 \cdot B(p+1)\) という関係式で求められます。

アルゴリズム

1. ビットカウント: \(M\) 個の \(Y_j\) について、各ビット位置の \(1\) の個数を配列 count に記録します。
2. 操作の適用: \(X\) の下位ビットから連続する \(0\) の個数 \(z\) を数え、操作回数 \(k = \min(K, z)\) を求めます。\(X\) を \(k\) 回操作した後の状態に更新し、そのビットを count に加算します。
3. スコア計算:
   • \(p = 1, \dots, N-1\) について、左側の総和 \(A[p]\) を前計算します。
   • \(p = N-1, \dots, 1\) について、右側の総和 \(B[p]\) を後ろから計算します。
4. 最大値の取得: すべての \(p\) における \(A[p] + B[p]\) の最大値を出力します。

計算量

• 時間計算量: \(O(MN)\)
  • \(M\) 個の \(Y_j\) のビットを走査するのに \(O(MN)\) かかります。
  • その後の \(p\) の探索は \(O(N)\) です。
  • \(N \le 46, M \le 2 \times 10^5\) より、全体で約 \(9.2 \times 10^6\) 回の操作となり、十分に高速です。
• 空間計算量: \(O(N)\)
  • 長さ \(N\) の配列 count, A, B を保持します。

実装のポイント

• 大きな値の処理: 答えは最大で \((M+1) \cdot 2^N\) 程度になります。制約上、signed 64-bit integer (long long) に収まることが保証されていますが、計算途中で溢れないよう注意が必要です。C++の場合は __int128 を使うとより安全に計算できます。

• ビット演算: \(X\) の操作後の値を作る際、(1LL << k) - 1 を用いて \(k\) 個の \(1\) が並んだマスクを作成し、それを \(N-k\) ビット左シフトすることで上位を \(1\) で埋めることができます。

  ソースコード

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

/**
 * Problem: Lamp sequence splitting score maximization
 * Takahashi has N lamps (0 or 1). Operation: if the leftmost is 0, shift right and add 1 at the end.
 * Max K operations. Then find a split position p (1 <= p <= N-1) for Takahashi's lamp string and
 * M additional lamp strings to maximize the sum of (left part value + right part value).
 */

int main() {
    // Faster I/O
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    long long N, K, M, X;
    if (!(cin >> N >> K >> M >> X)) return 0;

    // count[i] will store the total number of '1' bits at position i across all M+1 lamp strings.
    vector<long long> count(N, 0);

    // Read M additional lamp strings
    for (int i = 0; i < M; ++i) {
        long long Y;
        cin >> Y;
        for (int j = 0; j < N; ++j) {
            if ((Y >> j) & 1) {
                count[j]++;
            }
        }
    }

    // Determine the number of operations performed on Takahashi's lamp string X.
    // The operation shifts X right and adds a 1 at the (N-1)-th bit as long as the 0-th bit is 0.
    // This happens at most K times or until the 0-th bit becomes 1.
    long long z = 0;
    if (X == 0) {
        z = N;
    } else {
        long long tempX = X;
        while (z < N && (tempX & 1) == 0) {
            z++;
            tempX >>= 1;
        }
    }
    
    // Total operations k is the minimum of K and the number of leading zeros (from the right).
    long long k = min(K, z);
    if (k > 0) {
        if (k == N) {
            X = (1LL << N) - 1;
        } else {
            // After k operations, the first k bits are removed and k ones are added at the end.
            X = (X >> k) | (((1LL << k) - 1) << (N - k));
        }
    }

    // Add bits of the modified X to the count array.
    for (int j = 0; j < N; ++j) {
        if ((X >> j) & 1) {
            count[j]++;
        }
    }

    /**
     * For a split point p (1 <= p <= N-1):
     * Left part value for a string s: s & (2^p - 1)
     * Right part value for a string s: s >> p
     * Total A = sum of left parts = sum_{i=0}^{p-1} count[i] * 2^i
     * Total B = sum of right parts = sum_{i=p}^{N-1} count[i] * 2^{i-p}
     * We maximize A + B.
     */

    // Use __int128 for intermediate calculations to avoid overflow.
    // Although long long (64-bit) should be enough given the problem constraints.
    vector<__int128> A(N + 1, 0);
    vector<__int128> B(N + 1, 0);

    __int128 pow2 = 1;
    for (int i = 0; i < N; ++i) {
        A[i + 1] = A[i] + (__int128)count[i] * pow2;
        pow2 *= 2;
    }

    B[N] = 0;
    for (int i = N - 1; i >= 0; --i) {
        B[i] = (__int128)count[i] + 2 * B[i + 1];
    }

    __int128 max_val = 0;
    bool first_p = true;
    for (int p = 1; p < N; ++p) {
        __int128 current_score = A[p] + B[p];
        if (first_p || current_score > max_val) {
            max_val = current_score;
            first_p = false;
        }
    }

    // The final answer fits in a signed 64-bit integer.
    long long result = (long long)max_val;
    cout << result << endl;

    return 0;
}

この解説は gemini-3-flash-thinking によって生成されました。