kmjp's blog

競技プログラミング参加記です

Codeforces #434 Div1 A. Did you mean...

人が少なかったとか色々あるけど、初1位を取ったのにunratedだよ…。
http://codeforces.com/contest/860/problem/A

問題

アルファベット小文字で構成される単語で、同じでない子音が3つ以上続いているものはtypoと定義する。
文字列が与えられるので、最少の空白文字を挿入し、typoを0にせよ。

解法

貪欲で行ける。
前から順に文字を見て、「この文字を前の単語に連結させるとtypoが発生する」という場合、間に空白を挟めばよい。

同じ子音が3つ以上続くケースは問題ないことを用いて、うまく空白を配置させるとより良い結果が出る…なんてことはなさそうだ。

int N;
string S;

int cons[256];


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	FOR(i,256) cons[i]=1;
	cons['a']=0;
	cons['i']=0;
	cons['u']=0;
	cons['e']=0;
	cons['o']=0;
	
	
	cin>>S;
	string T;
	int hoge=0;
	FOR(i,S.size()) {
		char c=S[i];
		if(cons[c]==0) hoge=0;
		else hoge++;
		if(hoge>=3) {
			if(S[i]==S[i-1] && S[i]==S[i-2]) {
				hoge=3;
			}
			else {
				hoge=1;
				T+=' ';
			}
		}
		T+=c;
	}
	cout<<T<<endl;
	
}

まとめ

これで良いかちょっと迷った。