結果

問題 No.252 "良問"(良問とは言っていない (2)
コンテスト
ユーザー goodbaton
提出日時 2015-07-24 23:41:49
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 229 ms / 2,000 ms
コード長 2,314 bytes
コンパイル時間 778 ms
コンパイル使用メモリ 83,860 KB
実行使用メモリ 20,644 KB
最終ジャッジ日時 2024-07-16 00:27:25
合計ジャッジ時間 2,624 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 7
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:71:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   71 |     scanf("%d",&T);
      |     ~~~~~^~~~~~~~~

ソースコード

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