Codeforces #418 Div2 C An impassioned circulation of affection

コンテスト中に解けなかったやつ...

概要

文字列sが与えられる.(sの長さ $\leq1500$ )
クエリがq個飛んでくる(q $\leq200000$ )
各クエリはm( $1\leq m \leq n$ )と文字cが与えられる.
文字列sの文字のうちm個をcに書き換えた場合,部分文字列でcのみからなるも文字列の最長の長さを求めよ

解法

1.各文字cに対してs[0..i]に含まれるcの個数の累積和を求める.
2.累積和を用いて各文字cに対して,「長さi」のcからなる部分文字列を作るのに書き換える必要のある文字の数を求める
3.各クエリに対して「書き換える必要のある文字の数がm以下になっている最大の長さ」を(2)で求めた結果から計算する

計算量は $O(|s|q)$ でギリギリかな

コード

int n;
string s;
int q;
int m;
char c;

int main(){
    cin >> n >> s >> q;

    vector<vector<int>> cnt(26);
    for(char c='a';c<='z';c++){
        int i = c-'a';
        cnt[i] = vector<int>(n+10,0);
        for(int j=0;j<n;j++){
            if(s[j]==c) cnt[i][j+1] = cnt[i][j]+1;
            else cnt[i][j+1] = cnt[i][j];
        }
    }

    vector<vector<int>> need(26,vector<int>(n+10,0));
    for(char c='a';c<='z';c++){ //26
        for(int i=1;i<=n;i++){  //1500
            int mn = 0;
            for(int j=0;j<n;j++){
                int s = j;
                int t = s + i;
                if(t>n) break;
                // s[s..t)
                int num = cnt[c-'a'][t] - cnt[c-'a'][s];
                mn = max(mn,num);
            }
            need[c-'a'][i] = i-mn;
        }
    }

    rep(loop,q){
        cin >> m >> c;
        int ans = 0;
        for(int i=0;i<=n;i++){
            if(need[c-'a'][i] <= m) ans = i;
        }
        cout << ans << endl;
    }
}