結果

問題 No.252 "良問"(良問とは言っていない (2)
ユーザー machymachy
提出日時 2015-07-24 23:49:33
言語 C++11
(gcc 11.4.0)
結果
WA  
実行時間 -
コード長 1,187 bytes
コンパイル時間 626 ms
コンパイル使用メモリ 63,544 KB
実行使用メモリ 12,096 KB
最終ジャッジ日時 2024-07-16 00:33:08
合計ジャッジ時間 1,618 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 WA -
testcase_02 AC 40 ms
6,940 KB
testcase_03 AC 41 ms
12,072 KB
testcase_04 AC 41 ms
12,080 KB
testcase_05 AC 41 ms
12,096 KB
testcase_06 WA -
権限があれば一括ダウンロードができます

ソースコード

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] << " ";
            ans = min(ans, base + cost_f[i] + cost_b[i + 4]);
            if(i >= 7 && cost_b[i-7] == 0) base++;
        }
        //cerr << endl;
        cout << ans << endl;
    }

    return 0;
}
0