[Codeforces] Codeforces Round #668 (Div. 2) C. Balanced Bitstring

2020年9月8日

問題

方針

k-balanced な文字列は次の条件を満たします。\( s_i = 0 \) のとき、\(a_i = -1 \) とし、\(s_i = 1 \) のとき、\(a_i = 1 \) とすると、

\begin{eqnarray}
a_0 + a_1 + \cdots + a_{k-2} + a_{k-1}&=& 0\\
a_1 + a_2 + \cdots + a_{k-1} + a_{k}&=& 0\\
& \vdots & \\
a_{n-k} + a_{n-k} + \cdots a_{n-2} + a_{n-1}&=& 0\\
\end{eqnarray}

上二つの式から、\( a_0 = a_k \) であることが分かります。同様にして他の式にもついて考えると、\( a_i = a_{i + k} \) であるとが分かります。これは、

\[a_{i \bmod k} = a_{j \bmod k}\]

であることを示しています。したがって、上記が成立しているかどうかを調べます。次に、長さが \( k \) の部分文字列を \( t \) を構成した時、k-balanced な文字列にできるかどうかを調べます。

コード