結果

問題 No.150 "良問"(良問とは言っていない
コンテスト
ユーザー machy
提出日時 2015-07-25 18:24:32
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 3 ms / 5,000 ms
コード長 1,190 bytes
コンパイル時間 707 ms
コンパイル使用メモリ 62,968 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-10-11 01:55:32
合計ジャッジ時間 1,235 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

int calc_diff(string& s, int pos, const char* t){
    int ans = 0;
    for(int i = 0; t[i]; i++){
        if(s[pos + i] != t[i]) ans++;
    }
    return ans;
}

int main(){
    int T;
    cin >> T;
    for(int t = 0; t < T; t++){
        string s;
        cin >> s;
        vector<int> cost_f(s.size()+1, 11);
        vector<int> cost_b(s.size()+1, 11);
        for(int i = s.size() - 7; i >= 0; i--){
            cost_b[i] = min<int>(cost_b[i], calc_diff(s, i, "problem"));
            if(i < s.size() - 7) cost_f[i] = min(cost_f[i+1], cost_f[i]);
            //cerr << cost_b[i] << " ";
        }
        //cerr << endl;
        int ans = 11;
        int base = 0;
        for(int i = 0; i + 11 <= s.size(); i++){
            cost_f[i] = min<int>(cost_f[i], calc_diff(s, i, "good"));
            if(i > 0) cost_f[i] = min(cost_f[i], cost_f[i-1]);
            //cerr << cost_f[i] << " ";
            //if(i >= 7 && cost_b[i-7] == 0) base++;
            ans = min(ans, base + cost_f[i] + cost_b[i + 4]);
        }
        //cerr << endl;
        cout << ans << endl;
    }

    return 0;
}
0