概要

再帰的な分割で現れる各グループは、長さが \(2\) のべき乗で境界がそろった区間です。
区間長 \(K\) の部分を「赤が左、白が右」になるように並べ替える操作を高々 \(1\) 回行い、赤白の人数が等しいグループ数の最大値を求めます。

考察

グループはセグメント木の区間に対応する

生徒数を \(M=2^N\) とします。

再帰的に半分ずつ分割してできるグループは、次のような区間です。

• 全体区間
• 左半分・右半分
• さらにその半分
• \(\dots\)

これはちょうど、長さ \(M\) の配列に対する完全二分木、つまりセグメント木の各ノードに対応します。

ある区間の長さを \(L\) とすると、その区間が均衡グループである条件は

• 白帽の人数が \(L/2\)
• 赤帽の人数も \(L/2\)

であることです。

文字 1 を白帽とみなすと、区間内の 1 の個数が \(L/2\) なら均衡グループです。

なお、長さ \(1\) の区間は均衡グループにならないので、葉は数えません。

---

素朴に全候補を試すと間に合わない

操作する区間の左端は最大で \(M-K+1\) 通りあります。

各左端について、

1. 区間を並べ替える
2. すべてのグループについて均衡か判定する

とすると、各候補に \(O(M)\) 程度かかり、全体で \(O(M^2)\) になります。

\(M \leq 10^6\) なので、これは間に合いません。

---

隣り合う操作区間の結果は少ししか変わらない

重要な観察は、左端を \(l\) から \(l+1\) にずらしたとき、操作後の列は高々 \(4\) 箇所しか変化しないことです。

以降、添字は \(0\) 始まり、区間は半開区間 \([l,l+K)\) で考えます。

操作区間 \([l,l+K)\) に含まれる赤帽、つまり 0 の個数を \(z\) とします。
操作後の区間は

• \([l,l+z)\) が 0
• \([l+z,l+K)\) が 1

になります。

境界を

\[ p = l+z \]

とします。

次に左端を \(l+1\) にずらします。右端を \(r=l+K\) とすると、新しい区間は \([l+1,r+1)\) です。

新しい 0 の個数を \(z'\) とすると、

\[ z' = z - [S_l=0] + [S_r=0] \]

です。

0, 1 を数値として扱うと、これは

\[ z' = z + S_l - S_r \]

と書けます。

新しい境界は

\[ q = l+1+z' \]

です。

このとき

\[ q-p = 1 + S_l - S_r \]

なので、\(q-p\) は \(0,1,2\) のいずれかです。

つまり、境界の変化によって中身が変わる場所は高々 \(2\) 箇所です。

さらに、

• 左端 \(l\) は操作区間から外れる
• 右端 \(r\) は新しく操作区間に入る

ので、それぞれ高々 \(1\) 箇所ずつ変化します。

したがって、左端を \(1\) つずらすたびに、変化する場所は高々

\[ 1+2+1=4 \]

箇所だけです。

---

1 箇所の変化はセグメント木で更新できる

ある位置の値が 0 から 1、または 1 から 0 に変わったとします。

このとき影響を受けるグループは、その位置を含む区間だけです。
セグメント木で見ると、その位置の葉から根までの祖先ノードだけが影響を受けます。

祖先ノードの数は \(O(\log M)\) 個です。

各ノードについて、

• 更新前に均衡だったなら答え候補の個数を \(1\) 減らす
• 1 の個数を更新する
• 更新後に均衡なら答え候補の個数を \(1\) 増やす

とすれば、現在の均衡グループ数を保ったまま更新できます。

アルゴリズム

\(M=2^N\) とします。

1. 操作しない場合を計算する

まず、元の文字列 \(S\) について均衡グループ数を計算します。
これは答えの候補になります。

セグメント木の各ノードに、その区間に含まれる 1 の個数を持たせます。

区間長が \(L\) のノードについて、1 の個数が \(L/2\) なら均衡グループです。

---

2. 左端 \(0\) の操作結果を作る

次に、区間 \([0,K)\) を並べ替えた結果を作ります。

この区間内の 0 の個数を \(z\) とすると、

• \([0,z)\) を 0
• \([z,K)\) を 1

にします。

この状態についてもセグメント木を構築し、均衡グループ数を計算します。

---

3. 左端をスライドしながら更新する

現在の左端を \(l\)、右端を \(r=l+K\) とします。

現在の 0 の個数を \(z\)、境界を

\[ p=l+z \]

とします。

次の左端 \(l+1\) に対して、

\[ z' = z + S_l - S_r \]

\[ q = l+1+z' \]

を計算します。

変化する可能性がある位置は次の通りです。

左端 \(l\)

位置 \(l\) は操作区間から外れ、元の値 \(S_l\) に戻ります。

現在の位置 \(l\) は、\(z>0\) なら 0 です。
したがって、\(S_l=1\) かつ \(z>0\) のときだけ

\[ 0 \to 1 \]

の変化が起きます。

共通部分 \([l+1,r)\)

現在は境界 \(p\)、次は境界 \(q\) です。

\(q-p\) は高々 \(2\) なので、変化する場所は

\[ [p,q) \cap [l+1,r) \]

に含まれる高々 \(2\) 箇所だけです。

これらは

\[ 1 \to 0 \]

に変化します。

右端 \(r\)

位置 \(r\) は新しく操作区間に入ります。

新しい区間に 1 が少なくとも \(1\) つある、つまり \(z'<K\) なら、区間の最後である位置 \(r\) は 1 になります。

したがって、\(S_r=0\) かつ \(z'<K\) のときだけ

\[ 0 \to 1 \]

の変化が起きます。

---

4. 変化箇所ごとにセグメント木を更新する

ある位置が

• 0 から 1 になるなら +1
• 1 から 0 になるなら -1

として、その位置を含む全ノードの 1 の個数を更新します。

各ノードについて、更新前後で均衡かどうかを確認し、現在の均衡グループ数を更新します。

各左端について現在の均衡グループ数を答え候補に反映します。

最終的な最大値が答えです。

計算量

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

ただし \(M=2^N\) です。

最初のセグメント木構築と均衡グループ数の計算は \(O(M)\) です。
その後、左端を \(1\) つずらすたびに高々 \(4\) 箇所を更新し、各更新に \(O(\log M)\) かかるため、全体で \(O(M \log M)\) です。

実装のポイント

• セグメント木の各ノードには、その区間に含まれる 1 の個数を持たせます。

• 長さ \(2\) のノードなら 1 の個数が \(1\)、長さ \(4\) のノードなら 1 の個数が \(2\)、というように、区間長の半分と一致すれば均衡グループです。

• 葉、つまり長さ \(1\) の区間は均衡グループにならないので数えません。

• 操作しない場合も許されているため、元の文字列での均衡グループ数を必ず答え候補に入れます。

• 左端をスライドするときは、実際に区間全体を作り直さず、変化する高々 \(4\) 箇所だけを更新します。

  ソースコード

import sys

def main():
    input = sys.stdin.buffer.readline
    N, K = map(int, input().split())
    trans = bytes.maketrans(b'01', b'\x00\x01')
    s = input().strip().translate(trans)

    M = 1 << N
    base = M
    tree = [0] * (base * 2)

    def rebuild_count():
        t = tree
        for i in range(base - 1, 0, -1):
            t[i] = t[i << 1] + t[(i << 1) | 1]

        bal = 0
        start = base >> 1
        end = base
        half = 1
        while start:
            cnt = 0
            for i in range(start, end):
                if t[i] == half:
                    cnt += 1
            bal += cnt
            end = start
            start >>= 1
            half <<= 1
        return bal

    tree[base:base + M] = s
    original_bal = rebuild_count()

    z = K - sum(s[:K])

    tree[base:base + M] = s
    if z:
        tree[base:base + z] = bytes(z)
    ones = K - z
    if ones:
        tree[base + z:base + K] = b'\x01' * ones

    bal = rebuild_count()
    ans = original_bal if original_bal > bal else bal

    def add_delta(pos, delta, cur_bal):
        t = tree
        idx = (pos + base) >> 1
        half = 1
        while idx:
            x = t[idx]
            if x == half:
                cur_bal -= 1
            x += delta
            t[idx] = x
            if x == half:
                cur_bal += 1
            idx >>= 1
            half <<= 1
        return cur_bal

    p = z
    limit = M - K

    for l in range(limit):
        r = l + K
        sl = s[l]
        sr = s[r]

        z2 = z + sl - sr
        q = l + 1 + z2

        if sl and z:
            bal = add_delta(l, 1, bal)

        a = p
        lp1 = l + 1
        if a < lp1:
            a = lp1
        b = q
        if b > r:
            b = r

        if a < b:
            bal = add_delta(a, -1, bal)
            a += 1
            if a < b:
                bal = add_delta(a, -1, bal)

        if sr == 0 and z2 < K:
            bal = add_delta(r, 1, bal)

        z = z2
        p = q

        if bal > ans:
            ans = bal

    print(ans)

if __name__ == "__main__":
    main()

---

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