結果

問題 No.252 "良問"(良問とは言っていない (2)
ユーザー goodbatongoodbaton
提出日時 2015-07-24 23:41:49
言語 C++11
(gcc 4.8.5)
結果
AC  
実行時間 403 ms / 2,000 ms
コード長 2,314 Byte
コンパイル時間 545 ms
使用メモリ 18,568 KB
最終ジャッジ日時 2020-06-29 01:49:23

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
testcase_00 AC 218 ms
1,652 KB
testcase_01 AC 149 ms
1,616 KB
testcase_02 AC 386 ms
5,508 KB
testcase_03 AC 397 ms
18,568 KB
testcase_04 AC 403 ms
18,564 KB
testcase_05 AC 400 ms
18,564 KB
testcase_06 AC 2 ms
1,624 KB
権限があれば一括ダウンロードができます

ソースコード

diff #
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <string>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <cstring>

typedef long long ll;
using namespace std;

#define mod 1000003
#define INF 1000000000
#define LLINF 2000000000000000000LL

#define SIZE 100


struct RMQ{
    int segn2,seg[2<<20];

    RMQ(){
        segn2=0;
    }
    
    void init(int n){
        segn2=1;
        while(segn2<n) segn2*=2;
        
        for(int i=0;i<segn2*2-1;i++)
            seg[i]=2147483647;
    }

    int q(int a,int b,int l=0,int r=-1,int k=0){
        
        if(r<0) r=segn2-1;
        
        if(a<=l && r<=b) return seg[k];
        if(r<a || b<l) return 2000000000;
        
        return min(q(a,b,l,(l+r)/2,k*2+1),q(a,b,(l+r)/2+1,r,k*2+2));
    }

    void set(int k,int x){
        k+=segn2-1;
        seg[k]=x;
        
        while(k>0){
            k=(k-1)/2;
            seg[k]=min(seg[k*2+1],seg[k*2+2]);
        }
        
        return;
    }
};

RMQ rmq2;
int good[1000010];
int probc[1000010];


int main(){
    string S;
    int T,c,n,ans;
    
    scanf("%d",&T);
    
    for(int i=0;i<T;i++){
        
        ans = INF;
        
        cin >> S;
        n = (int)S.size();

        for(int i=0;i<n;i++){
            good[n]=INF;
            probc[i]=0;
        }
        
        rmq2.init(n);
        
        for(int j=0;j<n-3;j++){
            
            c=0;
            
            for(int i=0;i<4;i++){
                if(S[j+i]!="good"[i]){
                    c++;
                }
            }
            
            good[j]=c;
            
        }
        
        for(int j=0;j<n-6;j++){
            c=0;
            
            for(int i=0;i<7;i++){
                if(S[j+i]!="problem"[i]){
                    c++;
                }
            }
            
            if(c==0) probc[j+7]=1;
            
            rmq2.set(j,c);
        }
        
        
        for(int i=0;i<n-1;i++){
            probc[i+1]+=probc[i];
        }
        
        
        
        for(int i=0;i<n-10;i++){
            
            ans=min(ans,good[i]+rmq2.q(i+4,n-1)+probc[i]);
            
        }
        
        printf("%d\n",ans);
        
    }
    
    return 0;
}
0