/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 366 点
問題文
高橋君の部屋には N 個の照明が横一列に並んでおり、左から順に照明 1, 照明 2, \ldots, 照明 N と番号が付けられています。それぞれの照明は「点灯」または「消灯」のいずれかの状態になっています。各照明の初期状態は文字列 S で与えられます。S の i 文字目が 1 ならば照明 i は点灯、0 ならば消灯であることを表します。
高橋君は、すべての照明を点灯状態にしたいと考えています。高橋君は次の操作を 0 回以上任意の回数だけ行うことができます。
操作： 整数 l（1 \leq l \leq N - K + 1）を 1 つ選び、照明 l から照明 l + K - 1 までの連続する K 個の照明すべての状態を切り替える。すなわち、点灯している照明は消灯に、消灯している照明は点灯になる。各回の操作で選ぶ l の値は自由であり、異なる回で同じ値を選んでもかまわない。
すべての照明を点灯状態にすることが可能かどうか判定し、可能な場合は必要な最小の操作回数を求めてください。
制約
- 1 \leq N \leq 5 \times 10^5
- 1 \leq K \leq N
- S は長さ N の文字列であり、
0と1のみからなる - N, K は整数である
入力
N K S
- 1 行目には、照明の個数を表す整数 N と、一度に切り替える照明の個数を表す整数 K が、スペース区切りで与えられる。
- 2 行目には、各照明の初期状態を表す長さ N の文字列 S が与えられる。
出力
すべての照明を点灯状態にすることが可能な場合は、必要な最小の操作回数を 1 行で出力してください。不可能な場合は -1 を出力してください。
入力例 1
5 3 00100
出力例 1
2
入力例 2
5 3 01000
出力例 2
-1
入力例 3
10 2 0101010101
出力例 3
-1
入力例 4
20 5 00000000001111111111
出力例 4
2
入力例 5
1 1 1
出力例 5
0
Score : 366 pts
Problem Statement
In Takahashi's room, there are N lights arranged in a horizontal row, numbered from left to right as light 1, light 2, \ldots, light N. Each light is in one of two states: "on" or "off". The initial state of each light is given by a string S. If the i-th character of S is 1, then light i is on; if it is 0, then light i is off.
Takahashi wants to turn all the lights on. He can perform the following operation any number of times (including zero times).
Operation: Choose an integer l (1 \leq l \leq N - K + 1) and toggle the states of all K consecutive lights from light l to light l + K - 1. That is, lights that are on are turned off, and lights that are off are turned on. The value of l chosen in each operation is arbitrary, and the same value may be chosen in different operations.
Determine whether it is possible to turn all the lights on, and if so, find the minimum number of operations required.
Constraints
- 1 \leq N \leq 5 \times 10^5
- 1 \leq K \leq N
- S is a string of length N consisting only of
0and1 - N, K are integers
Input
N K S
- The first line contains an integer N representing the number of lights and an integer K representing the number of lights toggled at once, separated by a space.
- The second line contains a string S of length N representing the initial state of each light.
Output
If it is possible to turn all the lights on, output the minimum number of operations required in one line. If it is impossible, output -1.
Sample Input 1
5 3 00100
Sample Output 1
2
Sample Input 2
5 3 01000
Sample Output 2
-1
Sample Input 3
10 2 0101010101
Sample Output 3
-1
Sample Input 4
20 5 00000000001111111111
Sample Output 4
2
Sample Input 5
1 1 1
Sample Output 5
0