結果

問題 No.252 "良問"(良問とは言っていない (2)
ユーザー machymachy
提出日時 2015-07-24 23:50:56
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 79 ms / 2,000 ms
コード長 1,188 bytes
コンパイル時間 491 ms
コンパイル使用メモリ 63,684 KB
実行使用メモリ 12,080 KB
最終ジャッジ日時 2024-07-16 00:34:45
合計ジャッジ時間 1,270 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 33 ms
6,812 KB
testcase_01 AC 79 ms
6,944 KB
testcase_02 AC 36 ms
6,940 KB
testcase_03 AC 35 ms
12,080 KB
testcase_04 AC 39 ms
12,036 KB
testcase_05 AC 36 ms
11,988 KB
testcase_06 AC 2 ms
6,944 KB
権限があれば一括ダウンロードができます

ソースコード

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