E - トーナメント分割の均衡グループ 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 466 点

問題文

2^N 人の生徒が左から右に一列に並んでおり、各生徒は赤い帽子または白い帽子をかぶっています。生徒の帽子の色は、長さ 2^N の文字列 S で表されます。左から i 番目の生徒について、S の i 文字目が 0 なら赤い帽子、1 なら白い帽子をかぶっています。

高橋君は体育祭の準備として、次の操作を高々 1 回行うことができます。

  • ある整数 l（1 \leq l \leq 2^N - K + 1）を選び、左から l 番目から l+K-1 番目までの連続する K 人の生徒を並び替える。並び替えの結果、区間内の赤い帽子の生徒がすべて区間の左側に、白い帽子の生徒がすべて区間の右側に連続して配置される。区間外の生徒の位置は変わらない。

操作後（または操作を行わない場合はそのまま）、生徒たちは次のルールで再帰的にグループ分けされます。

  1. 最初に、左から 1 番目から 2^N 番目までの全生徒を 1 つのグループとする。
  2. 人数が 2 以上のグループは、左から数えて前半の生徒からなるグループと、後半の生徒からなるグループの 2 つに分割する。
  3. 各グループの人数が 1 になるまでこの分割を繰り返す。

この過程で現れるすべてのグループ（最初の全体グループ、途中の各段階のグループ、最終的な 1 人のグループをすべて含む、合計 2^{N+1} - 1 個）について考えます。あるグループにおいて、グループ内の赤い帽子の生徒の人数と白い帽子の生徒の人数が等しいとき、そのグループを「均衡グループ」と呼びます。なお、1 人のグループはこの条件を満たさないため、均衡グループにはなりません。

高橋君が操作の有無および区間の位置を最適に選んだとき、均衡グループの個数としてあり得る最大値を求めてください。

制約

  • 1 \leq N
  • 2^N \leq 10^6
  • 1 \leq K \leq 2^N
  • S は 0 と 1 からなる長さ 2^N の文字列
  • N, K は整数

入力

N K
S

1 行目には、生徒数のパラメータを表す整数 N と操作で並び替える区間の長さを表す整数 K がスペース区切りで与えられます。2 行目には、各生徒の帽子の色を表す長さ 2^N の文字列 S が与えられます。

出力

均衡グループの個数の最大値を 1 つの整数として出力してください。

入力例 1

2 2
0110

出力例 1

3

入力例 2

3 3
01011001

出力例 2

7

入力例 3

5 7
00110101111000010100111011001010

出力例 3

19

入力例 4

8 64
0100110010110001111001011010100011110000101010100101001111001100000111010010110111001000101101111010101000001111111100000101010101100110011010010101101011000011100100111011010001001011011110000011001111001100001111000011110011001010010101100011101010010111

出力例 4

146

入力例 5

1 1
01

出力例 5

1

Score : 466 pts

Problem Statement

2^N students are standing in a row from left to right, and each student is wearing either a red hat or a white hat. The hat colors of the students are represented by a string S of length 2^N. For the i-th student from the left, if the i-th character of S is 0, they are wearing a red hat, and if it is 1, they are wearing a white hat.

Takahashi, in preparation for the sports festival, can perform the following operation at most once:

  • Choose an integer l (1 \leq l \leq 2^N - K + 1), and rearrange the K consecutive students from the l-th to the (l+K-1)-th from the left. As a result of the rearrangement, all students with red hats within the interval are placed consecutively on the left side of the interval, and all students with white hats are placed consecutively on the right side of the interval. The positions of students outside the interval do not change.

After the operation (or as-is if no operation is performed), the students are recursively divided into groups according to the following rules:

  1. Initially, all students from the 1-st to the 2^N-th from the left form one group.
  2. A group with 2 or more people is split into two groups: one consisting of the first half of students (counted from the left) and one consisting of the second half.
  3. This splitting is repeated until each group contains exactly 1 person.

Consider all groups that appear during this process (including the initial whole group, groups at each intermediate stage, and the final single-person groups — a total of 2^{N+1} - 1 groups). A group is called a "balanced group" if the number of students with red hats and the number of students with white hats within the group are equal. Note that a single-person group cannot satisfy this condition, so it is never a balanced group.

Find the maximum possible number of balanced groups when Takahashi optimally chooses whether to perform the operation and the position of the interval.

Constraints

  • 1 \leq N
  • 2^N \leq 10^6
  • 1 \leq K \leq 2^N
  • S is a string of length 2^N consisting of 0 and 1
  • N, K are integers

Input

N K
S

The first line contains the integer N, which represents the parameter for the number of students, and the integer K, which represents the length of the interval to be rearranged in the operation, separated by a space. The second line contains the string S of length 2^N representing the hat color of each student.

Output

Output the maximum number of balanced groups as a single integer.

Sample Input 1

2 2
0110

Sample Output 1

3

Sample Input 2

3 3
01011001

Sample Output 2

7

Sample Input 3

5 7
00110101111000010100111011001010

Sample Output 3

19

Sample Input 4

8 64
0100110010110001111001011010100011110000101010100101001111001100000111010010110111001000101101111010101000001111111100000101010101100110011010010101101011000011100100111011010001001011011110000011001111001100001111000011110011001010010101100011101010010111

Sample Output 4

146

Sample Input 5

1 1
01

Sample Output 5

1