結果

問題 No.252 "良問"(良問とは言っていない (2)
ユーザー goodbatongoodbaton
提出日時 2015-07-24 23:41:49
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 300 ms / 2,000 ms
コード長 2,314 bytes
コンパイル時間 1,054 ms
コンパイル使用メモリ 84,968 KB
実行使用メモリ 20,376 KB
最終ジャッジ日時 2023-09-22 23:52:58
合計ジャッジ時間 2,999 ms
ジャッジサーバーID
(参考情報)
judge11 / judge14
このコードへのチャレンジ(β)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 159 ms
7,700 KB
testcase_01 AC 113 ms
7,680 KB
testcase_02 AC 300 ms
12,700 KB
testcase_03 AC 294 ms
20,280 KB
testcase_04 AC 295 ms
20,376 KB
testcase_05 AC 294 ms
20,268 KB
testcase_06 AC 2 ms
7,640 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