概要

まず高橋君のランプ列に対する操作後の状態をビット演算で求めます。
その後、各分割位置 \(p\) について「左側部分の値 + 右側部分の値」の総和を計算し、最大値を求めます。

考察

この問題で重要なのは、ランプ列の対応が通常の見た目とは逆である点です。

左から \(i\) 番目のランプ \(b_i\) は、整数の下から \(i\) ビット目に対応します。
つまり、

• 左端のランプ = 最下位ビット
• 右端のランプ = 最上位ビット

です。

操作後の高橋君のランプ列

操作では、左端のランプを見ます。
左端は整数でいう最下位ビットです。

• 最下位ビットが \(1\) なら終了
• 最下位ビットが \(0\) なら、それを取り除き、右端に \(1\) を追加する

これは整数で見ると、

• 下位ビットを \(1\) つ捨てる
• 上位に \(1\) を追加する

という操作です。

例えば、長さ \(N=5\) のランプ列が

\[ [0, 0, 1, 0, 1] \]

だったとします。左端が最下位ビットなので、この整数は下位から見て \(00101\) です。

左端に \(0\) が連続している間だけ操作が行われるので、操作回数は「\(X\) の末尾に連続する \(0\) の個数」、つまり trailing zeros によって決まります。

\(X \neq 0\) のとき、\(X\) の末尾に連続する \(0\) の個数を \(t\) とすると、実際に列が変化する回数は

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

です。

一方、\(X=0\) の場合は全ビットが \(0\) なので、最大で \(N\) 回まで操作できます。
したがって、

\[ r = \min(K, N) \]

です。

\(r\) 回操作した後の整数を \(tx\) とすると、

\[ tx = (X \gg r) \;|\; ((2^r - 1) \ll (N-r)) \]

になります。

ここで、

• \(X \gg r\) は、左端から \(r\) 個取り除いたことに対応
• \(((2^r - 1) \ll (N-r))\) は、右端に \(1\) を \(r\) 個追加したことに対応

しています。

分割位置 \(p\) のスコア

あるランプ列を表す整数を \(z\) とします。

分割位置 \(p\) を選ぶと、左側 \(p\) 個は整数 \(z\) の下位 \(p\) ビットです。
したがって左側部分の値は、

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

です。

右側部分は、\(p\) ビット分右にずらすことで得られます。
右側部分では改めて \(2^0\) から数え直すので、値は

\[ z \gg p \]

です。

よって、ランプ列 \(z\) に対する分割位置 \(p\) の寄与は、

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

です。

これを、高橋君の処理後のランプ列と、青木君の \(M\) 個のランプ列すべてについて足し合わせれば、その \(p\) における \(A+B\) が求まります。

\(N \leq 46\) なので、分割位置 \(p\) は最大でも \(45\) 通りしかありません。
各 \(p\) について \(M+1\) 個のランプ列を調べても十分高速です。

素朴に操作を \(K\) 回シミュレーションすると、\(K\) は最大 \(10^9\) なので間に合いません。
しかし、実際に必要なのは「先頭の \(0\) が何個続くか」だけなので、ビット演算で一気に求められます。

アルゴリズム

1. 入力を受け取る。
2. 高橋君の初期状態 \(X\) に対して、実際に変化する操作回数 \(r\) を求める。
   • \(X=0\) なら \(r=\min(K,N)\)
   • そうでなければ、\(X\) の trailing zeros を \(t\) として \(r=\min(K,t)\)
3. 操作後の高橋君の状態 \(tx\) を計算する。

$\( tx = (X \gg r) \;|\; ((2^r - 1) \ll (N-r)) \)$

1. 青木君の \(M\) 個の値に \(tx\) を追加し、合計 \(M+1\) 個のランプ列を考える。
2. 各分割位置 \(p=1,2,\ldots,N-1\) について、次を計算する。

$\( \sum_z \left((z \& (2^p - 1)) + (z \gg p)\right) \)$

1. その最大値を出力する。

計算量

• 時間計算量: \(O(NM)\)
• 空間計算量: \(O(M)\)

実装のポイント

\(X\) の trailing zeros は、Python では次のように求められます。

tz = (X & -X).bit_length() - 1

X & -X は、\(X\) の最下位の \(1\) ビットだけを取り出します。
それが \(2^t\) なら、trailing zeros の個数は \(t\) です。

また、\(M=0\) のときは入力の \(2\) 行目が存在しませんが、sys.stdin.buffer.read().split() でまとめて読むことで自然に処理できます。

ソースコード

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    N, K, M, X = data[0], data[1], data[2], data[3]

    if X == 0:
        r = K if K < N else N
    else:
        tz = (X & -X).bit_length() - 1
        r = K if K < tz else tz

    tx = (X >> r) | (((1 << r) - 1) << (N - r))

    vals = data[4:4 + M]
    vals.append(tx)

    ans = -1
    for p in range(1, N):
        mask = (1 << p) - 1
        s = 0
        for z in vals:
            s += (z & mask) + (z >> p)
        if s > ans:
            ans = s

    print(ans)

if __name__ == "__main__":
    main()

---

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