概要

左端が \(0\) の間だけ行われるランプ操作後の高橋君の列を求め、その列と \(M\) 個の列について、分割位置 \(p\) ごとのスコア \(A+B\) を計算し、最大値を求めます。

考察

操作後の高橋君の列

ランプ列は、左端が最下位ビットに対応しています。

現在の状態を整数 \(X\) とすると、左端のランプは最下位ビットです。

• 左端が \(1\) なら操作終了
• 左端が \(0\) なら、そのビットを取り除き、右端に \(1\) を追加する

これは整数で見ると、

\[ X \leftarrow (X \gg 1) \;|\; 2^{N-1} \]

という操作になります。

ただし、この操作が行われるのは左端が \(0\) の間だけです。

つまり、最初の \(X\) の下位ビットから連続する \(0\) の個数が重要です。
これを \(z\) とします。

例えば、下位ビット側から見て

\[ X = \cdots 101000 \]

であれば、連続する \(0\) は \(3\) 個なので \(z=3\) です。

操作は最大 \(K\) 回なので、実際に列が変化する回数は

\[ t = \min(K, z) \]

です。

ただし \(X=0\) の場合は、長さ \(N\) のビットがすべて \(0\) なので、\(z=N\) と考えます。

\(t\) 回操作した後の状態は、

• 元の \(X\) を \(t\) ビット右シフトする
• 右端に追加された \(t\) 個の \(1\) を上位側に立てる

ことで求められます。

したがって、操作後の値を \(X'\) とすると、

\[ X' = (X \gg t) \;|\; \left((2^t-1) \ll (N-t)\right) \]

です。

分割位置ごとのスコア

あるランプ列の状態を整数 \(S\) とします。

分割位置を \(p\) としたとき、左側 \(p\) 個は下位 \(p\) ビットです。
その値は

\[ S \& (2^p - 1) \]

です。

一方、右側部分は元の \(p+1\) 番目以降のビットですが、右側部分内では再び \(2^0\) から数え直します。
これは整数としては \(S\) を \(p\) ビット右シフトしたものです。

\[ S \gg p \]

よって、この列の分割位置 \(p\) における貢献は

\[ (S \& (2^p - 1)) + (S \gg p) \]

になります。

これを高橋君の操作後の列と、青木君の \(M\) 個の列すべてについて足し合わせれば、その \(p\) に対する \(A+B\) が得られます。

\(p\) は \(1 \le p \le N-1\) なので、全て試せばよいです。

素朴に各ビットを毎回見て計算すると余計な時間がかかりますが、ビット演算を使えば各列・各 \(p\) について \(O(1)\) で計算できます。

アルゴリズム

1. \(X\) の下位から連続する \(0\) の個数 \(z\) を求める。

   • \(X=0\) の場合は \(z=N\)
   • それ以外は __builtin_ctzll(X) で求められる

2. 実際に変化する操作回数を

$\( t = \min(K, z) \)$

とする。

1. 操作後の高橋君の列 \(finalX\) を計算する。

$\( finalX = X \gg t \)$

さらに \(t>0\) なら、上位 \(t\) ビットを \(1\) にする。

1. 各分割位置 \(p=1,2,\ldots,N-1\) について、合計値 sum[p] を用意する。

2. 高橋君の列 \(finalX\) について、

$\( (finalX \& (2^p-1)) + (finalX \gg p) \)$

を sum[p] に加える。

1. 各 \(Y_j\) についても同様に、すべての \(p\) に対して貢献を加える。

2. 最後に sum[p] の最大値を答えとする。

計算量

• 時間計算量: \(O((M+1)N)\)
• 空間計算量: \(O(N)\)

\(N \le 46\), \(M \le 2 \times 10^5\) なので、\(O(MN)\) で十分高速です。

実装のポイント

• \(N \le 46\) なので、値は 64-bit 整数で扱えます。

• ビットシフトでは 1ULL を使い、1 << p のような 32-bit 整数のオーバーフローを避けます。

• __builtin_ctzll(0) は未定義動作なので、\(X=0\) の場合は先に分岐して \(z=N\) とします。

• \(M=0\) の場合、2 行目の入力は存在しないので、読み込みループを単に 0 回にすれば問題ありません。

  ソースコード

#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;

    int z;
    if (X == 0) {
        z = N;
    } else {
        z = min(N, __builtin_ctzll(X));
    }

    int t = (int)min<long long>(K, z);

    unsigned long long finalX = (X >> t);
    if (t > 0) {
        finalX |= ((1ULL << t) - 1ULL) << (N - t);
    }

    vector<unsigned long long> mask(N);
    for (int p = 1; p <= N - 1; p++) {
        mask[p] = (1ULL << p) - 1ULL;
    }

    vector<unsigned long long> sum(N, 0);

    for (int p = 1; p <= N - 1; p++) {
        sum[p] += (finalX & mask[p]) + (finalX >> p);
    }

    for (int i = 0; i < M; i++) {
        unsigned long long Y;
        cin >> Y;
        for (int p = 1; p <= N - 1; p++) {
            sum[p] += (Y & mask[p]) + (Y >> p);
        }
    }

    unsigned long long ans = 0;
    for (int p = 1; p <= N - 1; p++) {
        ans = max(ans, sum[p]);
    }

    cout << ans << '\n';

    return 0;
}

---

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