結果

問題 No.150 "良問"(良問とは言っていない
ユーザー krotonkroton
提出日時 2015-05-26 20:46:44
言語 C++11
(gcc 4.8.5)
結果
AC  
実行時間 4 ms / 5,000 ms
コード長 1,188 Byte
コンパイル時間 982 ms
使用メモリ 6,876 KB
最終ジャッジ日時 2020-08-15 22:17:37
このコードへのチャレンジ(β)

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
testcase_00 AC 3 ms
6,876 KB
testcase_01 AC 2 ms
6,876 KB
testcase_02 AC 2 ms
6,872 KB
testcase_03 AC 2 ms
6,872 KB
testcase_04 AC 2 ms
6,876 KB
testcase_05 AC 2 ms
6,872 KB
testcase_06 AC 3 ms
4,824 KB
testcase_07 AC 2 ms
6,872 KB
testcase_08 AC 1 ms
4,828 KB
testcase_09 AC 2 ms
6,876 KB
testcase_10 AC 2 ms
6,872 KB
testcase_11 AC 3 ms
6,872 KB
testcase_12 AC 4 ms
4,824 KB
testcase_13 AC 2 ms
6,876 KB
testcase_14 AC 2 ms
6,876 KB
testcase_15 AC 2 ms
6,872 KB
testcase_16 AC 1 ms
4,832 KB
testcase_17 AC 2 ms
6,872 KB
testcase_18 AC 2 ms
4,824 KB
testcase_19 AC 3 ms
4,832 KB
testcase_20 AC 3 ms
6,876 KB
権限があれば一括ダウンロードができます

ソースコード

diff #
#include <bits/stdc++.h>
using namespace std;

const int INF = 1 << 25;
const string good = "good";
const string problem = "problem";

int main(){
    int T; cin >> T;
    
    while(T--){
        string S; cin >> S;
        
        int N = (int)S.size();
        vector<int> G(N, INF), P(N, INF);
        
        for(int i=0;i<N;i++){
            int t = i;
            int s = t - (int)good.size() + 1;
            if(s < 0)
                continue;
            
            int dif = 0;
            for(int j=0;j<good.size();j++){
                dif += S[s+j] != good[j];
            }
            
            G[i] = min(G[i-1], dif);
        }
        
        for(int i=N-1;i>=0;i--){
            int s = i;
            int t = s + (int)problem.size() - 1;
            if(t >= N)
                continue;
            
            int dif = 0;
            for(int j=0;j<problem.size();j++){
                dif += S[s+j] != problem[j];
            }
            
            P[i] = min(P[i+1], dif);
        }
        
        int res = INF;
        for(int i=1;i<N;i++)
            res = min(res, G[i-1] + P[i]);
        
        cout << res << endl;
    }
    
    return 0;
}
0