コンテンツにスキップ

スライディングウィンドウ

タグ「スライディングウィンドウ」の記事 1 件

SamCoding Round 7 (Div. 2) G - Chocolate Factory

D と M からなる長さ 2n−12n - 1 の文字列 ss が与えられます。長さ nn 以上の区間で、M をちょうど xx 個含むものが nn 個以上あるような xx を 1 つ求める問題です(n≤106n \le 10^6)。そのような xx は必ず存在します。

問題文では「nn 人の検査員がそれぞれ異なる区間を担当し、全員が同じ個数の M を検査する」という設定になっています。

たとえば n=3n = 3、s=s = MDMDM のとき、M を 22 個含む長さ 33 以上の区間は [1,3],[3,5],[1,4],[2,5][1, 3], [3, 5], [1, 4], [2, 5] の 44 個あるので、x=2x = 2 が答えです。

長さ nn 以上の区間はおよそ n22\frac{n^2}{2} 個あるので、すべて数えることはできません。そこで、条件を満たすと保証できる xx を 1 つ見つけます。

長さ nn の区間に含まれる M の個数の最大値を xx とすると、これが答えになります。

最大を達成する区間を [p,p+n−1][p, p + n - 1] とします。区間を 1 文字伸ばしたり縮めたりしても、M の個数は 00 か 11 しか変わりません。そのため、xx 以下の区間から xx 以上の区間まで 1 文字ずつ動かせば、途中に必ずちょうど xx の区間があります。

これを使って、ちょうど xx 個の区間を nn 個見つけます。

  • 左端 l<pl < p のそれぞれ(p−1p - 1 個): 右端を l+n−1l + n - 1 から p+n−1p + n - 1 まで伸ばしていきます。最初の [l,l+n−1][l, l + n - 1] は長さ nn なので M は xx 個以下、最後の [l,p+n−1][l, p + n - 1] は最大の区間を含むので xx 個以上です。途中に M がちょうど xx 個の区間があります。
  • 右端 r≥p+n−1r \ge p + n - 1 のそれぞれ(n−p+1n - p + 1 個): 左端を pp から r−n+1r - n + 1 まで縮めていきます。最初の [p,r][p, r] は最大の区間を含むので xx 個以上、最後の [r−n+1,r][r - n + 1, r] は長さ nn なので xx 個以下です。こちらも途中にちょうど xx 個の区間があります。

前者の区間は左端が pp より前、後者は左端が pp 以降なので、すべて異なります。どれも長さは nn 以上で、個数は (p−1)+(n−p+1)=n(p - 1) + (n - p + 1) = n です。

長さ nn の区間は nn 個あり、スライディングウィンドウで M の個数を更新しながら最大値を求めれば O(n)O(n) です。

Python
N = int(input())
S = input()
ans = t = S[:N].count("M")
for i in range(N - 1):
t -= S[i] == "M"
t += S[i + N] == "M"
ans = max(ans, t)
print(ans)

t が今の区間に含まれる M の個数です。区間を 1 つ右にずらすとき、左端から外れる S[i] と右端に入る S[i + N] の分だけ t を更新しています。