概要

長さ \(M\) の連続区間をすべて調べ、その中の 1 の個数が \(K\) 未満である区間の数を数える問題です。
各区間ごとに毎回 1 の個数を数え直すのではなく、スライディングウィンドウで高速に更新していきます。

考察

この問題では、区間は

• \(1\) 日目から \(M\) 日目
• \(2\) 日目から \(M+1\) 日目
• \(3\) 日目から \(M+2\) 日目
• …

のように、1 日ずつ右へずれていきます。

素朴な方法

各区間ごとに、長さ \(M\) の部分文字列の中にある 1 の個数を毎回数える方法を考えると、

• 区間の数は \(N - M + 1\)
• 1 区間を数えるのに \(O(M)\)

なので、全体で \(O((N-M+1) \times M)\)、最悪では \(O(NM)\) になります。

制約は \(N \leq 10^6\) なので、たとえば \(M\) も同じくらい大きいと非常に間に合いません。

重要な気づき

隣り合う区間は、ほとんど同じ要素を含んでいます。

たとえば区間

• \([i-M+1, i]\)
• \([i-M+2, i+1]\)

を比べると、

• 左端の 1 文字が抜ける
• 右端に 1 文字が追加される

だけです。

つまり、前の区間の 1 の個数が分かっていれば、

• 抜ける文字が 1 なら \(-1\)
• 入る文字が 1 なら \(+1\)

とするだけで、次の区間の 1 の個数が求められます。

これにより、各区間を \(O(1)\) で処理でき、全体を \(O(N)\) にできます。

具体例

たとえば

• \(S =\) 10110
• \(M = 3\)
• \(K = 2\)

とします。

最初の区間 101 の 1 の個数は \(2\) です。
次の区間は 011 ですが、これは前の区間から

• 左端の 1 が抜ける → \(-1\)
• 右端の 1 が入る → \(+1\)

なので、個数は引き続き \(2\) だとすぐ分かります。

このように毎回数え直さずに更新していけば高速です。

アルゴリズム

1. 最初の長さ \(M\) の区間 S[:M] に含まれる 1 の個数を数える。
2. その個数が \(K\) 未満なら答えに \(1\) を足す。
3. その後、右へ 1 文字ずつ区間をずらしながら次を行う。
   • 区間から抜ける文字 S[i-M] が 1 なら個数を \(1\) 減らす
   • 新しく入る文字 S[i] が 1 なら個数を \(1\) 増やす
   • 更新後の個数が \(K\) 未満なら答えに \(1\) を足す
4. 最後に答えを出力する。

この方法が、いわゆる スライディングウィンドウ です。

計算量

• 時間計算量: \(O(N)\)
• 空間計算量: \(O(1)\)

実装のポイント

• 最初の区間の 1 の数は S[:M].count('1') で求めています。

• その後は毎回数え直さず、抜ける文字と入る文字だけを見て更新します。

• ループ for i in range(M, N): では、S[i] が新しく入る文字、S[i-M] が抜ける文字になります。

• 入力サイズが大きいので、sys.stdin.readline を使って高速に入力しています。

  ソースコード

import sys

def main():
    input = sys.stdin.readline
    N, M, K = map(int, input().split())
    S = input().strip()

    cnt = S[:M].count('1')
    ans = 1 if cnt < K else 0

    for i in range(M, N):
        if S[i - M] == '1':
            cnt -= 1
        if S[i] == '1':
            cnt += 1
        if cnt < K:
            ans += 1

    print(ans)

if __name__ == "__main__":
    main()

---

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