yukicoder : No.996 Phnom Penh

なんか変わった問題設定。
https://yukicoder.me/problems/no/996

問題

文字列Sが与えられる。
以下の処理を、文字列に変化が起きる限り任意回数任意順に起こせる場合、最大何回処理を行えるか。
A. "phnom"を1か所"penh"にする。
B, "h"をすべて消したのち"e"をすべて"h"にする。

解法

この処理は以下の特性がある。

• 処理Aを1回行うと、その位置で再度Aを行うことはできない。
• 処理Bを2連続行うと"e""h"が完全消滅するので、以後前者も後者もできない。
• 処理A→Bの順で行うと、phnom→penh→phnとなり"om"が1個消える。

とすると選択肢は
(処理Bを0回か1回) + (処理Aをできる限り行って処理Bを1回)×できるだけ + (処理Bを1回)
の一択である。
最初の処理Bの有無以外は処理が確定するので、そこは2通り試そう。

あとは真ん中の処理を何回行うかである。
まず、文字列中の雑多な(phnomやpenh周辺以外の)hやeを消すため2周は愚直に回そう。
あとは3つ目の特性とり、phn(om)*nのパターンを見つければ、処理Aをsum(n)回、処理Bをmax(n)回行えることになる。

int N;
string S;

int hoge(string S) {
	int i,j;
	int ret=0;
	FOR(i,100) {
		string R;
		FORR(c,S) {
			R+=c;
			if(R.size()>=5 && R.substr(R.size()-5)=="phnom") {
				R=R.substr(0,R.size()-5)+"penh";
				ret++;
			}
		}
		if(count(ALL(R),'h')||count(ALL(R),'e')) {
			S="";
			ret++;
			FORR(c,R) {
				if(c=='h') continue;
				if(c=='e') S+='h';
				else S+=c;
			}
		}
		else {
			S=R;
		}
	}
	int ma=0;
	
	FOR(i,(int)S.size()-4) {
		if(S.substr(i,5)=="phnom") {
			for(j=i+3;j<S.size()-1;j+=2) {
				if(S[j]!='o' || S[j+1]!='m') break;
				ret++;
				ma=max(ma,(j-i)/2+1);
			}
			i=j-1;
		}
	}
	if(ma==0 && count(ALL(S),'e')) ma=2;
	if(ma==0 && count(ALL(S),'h')) ma=1;
	ret+=ma;
	return ret;
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>S;
	int ret=hoge(S);
	if(count(ALL(S),'h')||count(ALL(S),'e')) {
		string R;
		FORR(c,S) {
			if(c=='h') continue;
			if(c=='e') c='h';
			R+=c;
		}
		ret=max(ret,1+hoge(R));
	}
	cout<<ret<<endl;
}

まとめ

phnom penhってプノンペンのことなのね。