結果

問題 No.252 "良問"(良問とは言っていない (2)
ユーザー IL_mstaIL_msta
提出日時 2015-07-25 02:45:59
言語 C++11
(gcc 11.4.0)
結果
TLE  
実行時間 -
コード長 2,599 bytes
コンパイル時間 954 ms
コンパイル使用メモリ 89,944 KB
実行使用メモリ 16,952 KB
最終ジャッジ日時 2024-07-16 04:32:26
合計ジャッジ時間 7,205 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 TLE -
testcase_01 -- -
testcase_02 -- -
testcase_03 -- -
testcase_04 -- -
testcase_05 -- -
testcase_06 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#define _USE_MATH_DEFINES
 
#include <iostream>
#include <iomanip>
#include <sstream>
 
#include <algorithm>
#include <cmath>
 
#include <string>
//#include <array>
#include <list>
#include <queue>
#include <vector>
#include <complex>
#include <set>
#include <map>
 
/////////
#define REP(i, x, n) for(int i = x; i < n; i++)
#define rep(i,n) REP(i,0,n)
#define P(p) cout<<(p)<<endl;
 
#define PII pair<int,int>
/////////
typedef long long LL;
typedef long double LD;
/////////
using namespace::std;
/////////
int ans[100000];

bool check(string str){
	int a,b;
	a = str.find("good");
	if(a == -1){
		return false;
	}
	b = str.find("problem",a);
	if( b == -1){
		return false;
	}
	return true;
}
int ter1,termin1;
int ngit,ngit2;
int ngcount,ngcount2;
int ser(string str,string ter,string ng){
	//strからter作る ngがあってはだめ
	int ans=ter.size()+1,tans;
	ans = min(ans,termin1);
	for(unsigned int i=ter1; i+4 <= str.size(); ++i){
		tans = 0;
		for(unsigned int len=0;len < ter.size() && i+len < str.size() ; ++len){
			if( str[i+len] != ter[len]){
				++tans;
			}
		}
		ans = min(ans,tans);
		++ter1;
		termin1 = min(termin1,ans);
	}
	////
	int it = ngit;
	int temp;
	int count = ngcount;
	ans += ngcount;
	for(;;){
		temp = str.find(ng,it);
		if(temp == -1){
			break;
		}
		it = temp+1;
		++count;
		++ans;
	}
	ngit = it;
	ngcount = count;
	return ans;
}

int ser2(string str,string ter,string ng){
	//strからter作る ngがあってはだめ
	int ans=ter.size()+1,tans;
	int temp,it=0;
	int count = 0;
	string tStr;
	for(unsigned int i=0;i+7<=str.size();++i){
		tans = 0;
		//0,i-1までにng
		tStr = str.substr(0,i);
		it = 0;
		for(;;){
			temp = tStr.find(ng,it);
			if(temp == -1){
				break;
			}
			it = temp + 1;
			++tans;
		}

		for(unsigned int len=0;len < ter.size() && i+len < str.size() ; ++len ){
			if( str[i+len] != ter[len]){
				++tans;
			}
		}
		ans = min(ans,tans);
	}
	
	return ans;
}

int solve(string str){
	ter1 = 0;
	termin1 = 4;
	ngit=0;
	ngit2 =0;
	ngcount=0;
	ngcount2=0;
	//goodp roble m
	int ans = 12,tans;
	string Astr,Bstr;
	for(unsigned int i=0;i+11<=str.size();++i){
		Astr = str.substr(0,i+4);
		tans = ser(Astr, "good","problem");
		if(ans <= tans)continue;
		Bstr = str.substr(i+4,str.size()-i-4 );
		tans += ser2(Bstr,"problem","good");
		ans = min(ans,tans);
	}

	return ans;
}
int main(void){
    std::cin.tie(0); 
    std::ios::sync_with_stdio(false);
    std::cout << std::fixed;//
    //cout << setprecision(16);//
	
	int T;
	cin>>T;
	string str;
	rep(i,T){
		cin>>str;
		ans[i] = solve(str);
	}
	rep(i,T){
		P(ans[i]);
	}
	return 0;
}
0