[1] 判定問題を解く

\(S\) に含まれる 1 の数を \(M\) とします。

各 \(i\ (1\le i \le N-K+1)\) に対し、\(S_i,\ S_{i+1},\ \dots, S_{i+K-1}\) をすべて 1 にしてそれ以外を 0 にできるかを考えます。これは

• \(S_i,\ S_{i+1},\ \dots,\ S_{i+K-1}\) のなかの 1 の数は \(M\)
• \(S_i,\ S_{i+1},\ \dots,\ S_{i+K-1}\) のなかの 0 の数は \(0\)

が必要十分条件です。これを各 \(i\) に対し調べ、条件を満たす \(i\) が \(1\) 個になれば答えは Yes 、ならなければ No になります。

[2] \(S_i,\ S_{i+1},\ \dots,\ S_{i+K-1}\) のなかの 1 を高速に数える

\(S_i,\ S_{i+1},\ \dots,\ S_{i+K-1}\) のなかの 1 の数を愚直にしらべると \(\Theta(NK)\) だけかかってしまい、テストケースによっては実行時間制限に間に合いません。

これは \(i\rightarrow i+1\) での個数の変化に着目することで改善できます。具体的には、\(S_i,\ S_{i+1},\ \dots,\ S_{i+K-1}\) のなかの 1 の数と\(S_{i+1},\ S_{i+2},\ \dots,\ S_{i+K}\) のなかの 1 の数の違いは \(S_i,\ S_{i+K}\) でしか生じません。よって前者が求まっていれば後者の値は \(O(1)\) で求まります。

以上より各 \(i\ (1\le i \le N-K+1)\) に対する \(S_i,\ S_{i+1},\ \dots,\ S_{i+K-1}\) のなかの 1 の数は、全体で \(O(N)\) で求めることができます。

0 の数についても同様の方法で \(O(N)\) で求めることができます。

これらの求めた値を利用すれば判定問題も \(O(1)\) で解けるので、この問題は \(O(N)\) で解くことができます。