kmjp's blog

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

UTPC 2014 : A - 二重否定除去法則

UTPCに参加。ラスト40秒で部分点を取って1ページ目に。
200ptまでは解けたけど、300ptが一つも解けない(そもそも問題文見る時間すらない)だった。
http://utpc2014.contest.atcoder.jp/tasks/utpc2014_a

問題

英単語群からなる文章Sが与えられる。
"not not (not以外の単語)"という部分文字列があったら、"not not "を削除したものを答えよ。

解法

Sを後ろから見ていって、S[x]のprefixが"not not "であり、かつprefixが"not not not\0"や"not not not "出ない場合、"not not "を削除すればよい。

char SS[5050];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	gets(SS);
	l=strlen(SS);
	if(SS[l-1]=='\n') SS[--l]=0;
	for(x=l;x>=0;x--) {
		if(x&&SS[x-1]!=' ') continue;
		if(memcmp(SS+x,"not not not ",12)==0) continue;
		if(memcmp(SS+x,"not not not",11)==0 && SS[x+11]==0) continue;
		if(memcmp(SS+x,"not not ",8)==0) {
			for(y=x+8;y<l+10;y++) SS[y-8]=SS[y];
			l-=8;
			x--;
		}
	}
	_P("%s\n",SS);
}

まとめ

本番、改行のあるなしの処理で戸惑って3WAもしてしまった。