D - Longest X Editorial by sugarrr


この問題は尺取り法というアルゴリズムを用いて解くことができます。
尺取り法とは端的に言うと、区間の左端と右端を尺取り虫のように動かすことで、条件を満たす区間を高速に見つける、というアルゴリズムです。

擬似コードで書くと以下のようになります。

r=0, ans=0
for l = 0 to |S| - 1
    while S[l,r+1)をすべて 'X' に変えることが可能
        r = r + 1
    ans = max(ans, r - l)

なお、擬似コード \(3\) 行目の

\(S[l,r+1)\) をすべて X に変えることが可能か? \(\cdots(*)\)

の判定は、ある程度高速に行う必要があります。
たとえば、前計算として . の数の累積和を求めておくと、\((*)\)\(O(1)\) で判定することができます。

全体の計算量は \(O(|S|)\) です。

C++ による実装例

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

signed main(){
    string s;cin>>s;
    ll k;cin>>k;
    ll n=s.size();

    vector<ll>cnt(n+1); //累積和
    for(ll i=0;i<=n-1;i++){
        if(s[i]=='.')cnt[i+1] = cnt[i] + 1;
        else cnt[i+1] = cnt[i];
    }// cnt[r] - cnt[l] で s[l,r) の '.' の数を表す

    ll ans = 0;
    ll r = 0;
    for(ll l=0;l<=n-1;l++){
        while(r<=n-1 && cnt[r+1]-cnt[l] <= k){
            r = r+1;
        }
        ans = max(ans,r-l);
    }
    cout<<ans<<endl;
    return 0;
}

posted:
last update: