概要

この問題は、完全二分木の構造を持つグループ分けにおいて、特定の区間をソートする操作を1回だけ行い、赤い帽子と白い帽子の数が等しい「均衡グループ」の数を最大化する問題です。

考察

1. グループの構造

\(2^N\) 人の生徒は、長さ \(2^k\) (\(1 \le k \le N\)) の特定の区間に固定されてグループ化されます。 - グループの総数は \(2^{N+1}-1\) 個です。 - 各深さ \(k\) において、グループの開始位置 \(L\) は必ず \(2^k\) の倍数になります。 - グループ \(G = [L, R)\) が均衡であるとは、その区間内の 1 の個数が \((R-L)/2\) であることを指します。

2. 操作の影響

長さ \(K\) の区間 \([l, l+K)\) をソートすると、その区間内の 0 が左側に、1 が右側に固まります。この操作によって各グループの状態は以下の3パターンに変化します。 1. 区間の外側にあるグループ: 状態は変わりません。 2. 区間に完全に含まれるグループ: ソート後の 1 の配置によって、均衡になるかどうかが決まります。 3. 区間と部分的に重なるグループ: 境界部分で 1 の数が変化するため、再計算が必要です。

3. 効率的な計算の工夫

すべての \(l\) (\(0 \le l \le 2^N-K\)) について均衡グループの数を愚直に数えると \(O(2^N \cdot 2^N)\) となり間に合いません。そこで、以下の工夫を行います。

• 初期状態のカウント: 操作前の均衡グループの総数 Base を求めておきます。
• 差分更新: 操作範囲 \([l, l+K)\) に完全に含まれる既存の均衡グループの数を、いもす法（累積和）を用いて事前に計算しておきます。これにより、操作によって「一旦リセットされる」均衡グループの数を高速に引くことができます。
• ソート後の均衡判定:
  • 完全に含まれる場合: ソート後、1 は \([l+K-C, l+K)\) の範囲に並びます（\(C\) は区間内の 1 の総数）。サイズ \(2^k\) のグループ \(G=[L, R)\) が均衡になるのは、1 と 0 の境界 \(l+K-C\) がグループのちょうど真ん中 \(L + 2^{k-1}\) に来るときだけです。
  • 部分的に重なる場合: 各深さ \(k\) について、左端 \(l\) を跨ぐグループと右端 \(l+K\) を跨ぐグループはそれぞれ最大1つずつしかありません。これらを個別に判定します。

アルゴリズム

1. 累積和 \(P\) を作成し、任意の区間の 1 の個数を \(O(1)\) で取得できるようにします。
2. 事前準備:
   • 全グループを走査し、初期状態で均衡なグループを数える (Base)。
   • いもす法を用い、各 \(l\) について「\([l, l+K)\) に完全に含まれる初期均衡グループの数」を count_balanced_in_S[l] に格納する。
3. メインループ: 各 \(l \in [0, 2^N-K]\) について以下を計算する。
   • 現在の均衡数 current_f = Base - count_balanced_in_S[l]。
   • 各 \(k \in [1, N]\) について：
     • 部分重複の処理: \(l\) または \(l+K\) を含むグループのソート前後の均衡状態を確認し、current_f を増減させる。
     • 完全包含の処理: 境界位置 \(l+K-C\) から逆算して、均衡になり得る唯一の開始位置 \(L = l+K-C-2^{k-1}\) が、正しいグループの開始位置（\(2^k\) の倍数）かつ \([l, l+K)\) 内にあるか判定する。
4. current_f の最大値を出力する。

計算量

• 時間計算量: \(O(N \cdot 2^N)\)
  • 累積和の構築: \(O(2^N)\)
  • いもす法による事前計算: \(O(N \cdot 2^N / 2^k)\) の合計 ＝ \(O(2^N)\)
  • メインループ: \(2^N\) 回のループ内で \(N\) 回のレベル処理を行うため \(O(N \cdot 2^N)\)。
• 空間計算量: \(O(2^N)\)
  • 累積和配列やいもす用配列に \(O(2^N)\) のメモリを使用します。

実装のポイント

• ビット演算: グループの開始位置 \(L\) が \(2^k\) の倍数であるかの判定 (L & (size - 1)) == 0 や、端点を含むグループの特定 (l >> k) << k など、ビット演算を活用することで簡潔に記述できます。

• 境界条件: ソート範囲の境界で 1 がどのように分布するか（c1_new の計算）を正確にシミュレーションする必要があります。特に、ソートされた 1 の区間 \([l+K-C, l+K)\) と、注目しているグループの重なりを慎重に計算します。

  ソースコード

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

using namespace std;

/**
 * Problem: Balanced Groups in Tournament Split
 * The tournament structure forms a perfect binary tree of groups.
 * A group is balanced if it has an equal number of '0's and '1's.
 * We can perform at most one operation: sort a range of length K.
 * Sorting a range [l, l+K) makes all '0's come first, then all '1's.
 * Goal: Maximize the number of balanced groups.
 */

int main() {
    // Optimize standard I/O
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, K;
    if (!(cin >> N >> K)) return 0;
    string S;
    cin >> S;

    // M is the total number of students (2^N)
    int M = 1 << N;
    
    // P is the prefix sum array of the number of '1's in S
    vector<int> P(M + 1, 0);
    for (int i = 0; i < M; ++i) {
        P[i + 1] = P[i] + (S[i] - '0');
    }

    // Base: number of balanced groups in the original string S
    // diff: difference array for imos to count balanced groups contained in range [l, l+K)
    int Base = 0;
    vector<int> diff(M + 2, 0);
    for (int k = 1; k <= N; ++k) {
        int size = 1 << k;
        int half = size >> 1;
        for (int L = 0; L <= M - size; L += size) {
            int R = L + size;
            if (P[R] - P[L] == half) {
                Base++;
                // If group G = [L, R) is balanced in S, it contributes to Base.
                // If G is entirely within the operation range [l, l+K), it will be handled separately.
                // G is a subset of [l, l+K) if l <= L and R <= l+K.
                // This is equivalent to l in [R-K, L].
                int l_min = max(0, R - K);
                int l_max = min(M - K, L);
                if (l_min <= l_max) {
                    diff[l_min]++;
                    diff[l_max + 1]--;
                }
            }
        }
    }

    // count_balanced_in_S[l] = number of balanced groups in S that are subsets of [l, l+K)
    vector<int> count_balanced_in_S(M + 1, 0);
    int cur = 0;
    for (int l = 0; l <= M - K; ++l) {
        cur += diff[l];
        count_balanced_in_S[l] = cur;
    }

    // max_f stores the maximum number of balanced groups found
    int max_f = Base;

    // Iterate over every possible starting position l of the range [l, l+K)
    for (int l = 0; l <= M - K; ++l) {
        // c_op: number of '1's in the range being sorted
        int c_op = P[l + K] - P[l];
        
        // Start with Base, subtract balanced groups in S that are inside the sorted range
        int current_f = Base - count_balanced_in_S[l];

        for (int k = 1; k <= N; ++k) {
            int size = 1 << k;
            int half = size >> 1;
            
            // 1. Groups that partially overlap with [l, l+K)
            // Case A: L < l < R < l+K (Group contains l but not l+K-1, and starts before l)
            int L1 = (l >> k) << k;
            int R1 = L1 + size;
            if (L1 < l && R1 < l + K) {
                if (P[R1] - P[L1] == half) current_f--;
                // After sorting [l, l+K), '1's in [l, l+K) are at the end.
                // The number of '1's in the intersection [l, R1) is:
                int c1_new = (P[l] - P[L1]) + max(0, R1 - max(l, l + K - c_op));
                if (c1_new == half) current_f++;
            }

            // Case B: l < L < l+K < R (Group contains l+K-1 but not l, and ends after l+K)
            int L2 = ((l + K - 1) >> k) << k;
            int R2 = L2 + size;
            if (L2 > l && R2 > l + K) {
                if (P[R2] - P[L2] == half) current_f--;
                // The number of '1's in the intersection [L2, l+K) is:
                int c1_new = (P[R2] - P[l + K]) + max(0, (l + K) - max(L2, l + K - c_op));
                if (c1_new == half) current_f++;
            }

            // 2. Groups G = [L, R) that are subsets of [l, l+K)
            // After sorting, G is balanced if its intersection with the sorted '1's is size/2.
            // This happens if the start of the '1's in the sorted range [l, l+K) 
            // is exactly the midpoint of the group G.
            // Midpoint of G is L + size/2. Start of '1's is l + K - c_op.
            // So L + size/2 = l + K - c_op  =>  L = l + K - c_op - size/2.
            int L3 = l + K - c_op - half;
            if (L3 >= 0 && (L3 & (size - 1)) == 0) {
                int R3 = L3 + size;
                if (l <= L3 && R3 <= l + K) {
                    current_f++;
                }
            }
        }
        if (current_f > max_f) max_f = current_f;
    }

    cout << max_f << endl;

    return 0;
}

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