結果

問題 No.252 "良問"(良問とは言っていない (2)
ユーザー machymachy
提出日時 2015-07-24 23:47:49
言語 C++11
(gcc 11.4.0)
結果
WA  
実行時間 -
コード長 1,178 bytes
コンパイル時間 531 ms
コンパイル使用メモリ 65,332 KB
実行使用メモリ 12,076 KB
最終ジャッジ日時 2023-09-22 23:57:07
合計ジャッジ時間 1,490 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge15
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 37 ms
4,376 KB
testcase_01 AC 84 ms
4,376 KB
testcase_02 AC 40 ms
5,416 KB
testcase_03 AC 40 ms
12,076 KB
testcase_04 AC 40 ms
11,840 KB
testcase_05 AC 40 ms
11,968 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(cost_b[i+4] == 0) base++;
        }
        //cerr << endl;
        cout << ans << endl;
    }

    return 0;
}
0