SamCoding Round 7 (Div. 2) G - Chocolate Factory
- サイト
- SamCoding
- コンテスト
- SamCoding Round 7 (Div. 2)
- 問題
- G - Chocolate Factory(常設版)
D と M からなる長さ の文字列 が与えられます。長さ 以上の区間で、M をちょうど 個含むものが 個以上あるような を 1 つ求める問題です()。そのような は必ず存在します。
問題文では「 人の検査員がそれぞれ異なる区間を担当し、全員が同じ個数の M を検査する」という設定になっています。
たとえば 、 MDMDM のとき、M を 個含む長さ 以上の区間は の 個あるので、 が答えです。
長さ 以上の区間はおよそ 個あるので、すべて数えることはできません。そこで、条件を満たすと保証できる を 1 つ見つけます。
長さ の区間に含まれる M の個数の最大値を とすると、これが答えになります。
が条件を満たす理由
Section titled “xxx が条件を満たす理由”最大を達成する区間を とします。区間を 1 文字伸ばしたり縮めたりしても、M の個数は か しか変わりません。そのため、 以下の区間から 以上の区間まで 1 文字ずつ動かせば、途中に必ずちょうど の区間があります。
これを使って、ちょうど 個の区間を 個見つけます。
- 左端 のそれぞれ( 個): 右端を から まで伸ばしていきます。最初の は長さ なので
Mは 個以下、最後の は最大の区間を含むので 個以上です。途中にMがちょうど 個の区間があります。 - 右端 のそれぞれ( 個): 左端を から まで縮めていきます。最初の は最大の区間を含むので 個以上、最後の は長さ なので 個以下です。こちらも途中にちょうど 個の区間があります。
前者の区間は左端が より前、後者は左端が 以降なので、すべて異なります。どれも長さは 以上で、個数は です。
長さ の区間は 個あり、スライディングウィンドウで M の個数を更新しながら最大値を求めれば です。
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 を更新しています。