読者です 読者をやめる 読者になる 読者になる

kmjp's blog

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

Codeforces #163 Div2. A. Stones on the Table, B. Queue at the School

さて#163。今回が初本戦参加。
A,Bだけ極端に簡単だったが、両方で1回ずつしょうもないミスをしてひどい順位になった。
ただ、なんとかCを解ききったらまぁまぁな順位でギリギリDiv1昇格になりました。
その後Dも本番時間中に方向性を定めて、その後ノーヒントで解けたしDまで解ききりたかったところ。

では最初の2問から。
http://codeforces.com/contest/266/problem/A
http://codeforces.com/contest/266/problem/B

A. Stones on the Table

最大50文字で、1列に並んだ石の色がRGBで与えられる。
いくつか石を取り除いて隣接する石の色が異なるようにしたい。
取り除くべき石の数の最少の値を答える問題。

これは単純に、同じ色が隣接していたらどちらかを取り除けばよいので、単に隣接する色が同じなら取り除く数をインクリメントするだけ。

int N;

void solve() {
	int f,r,i,j,k,l;
	char str[100];
	int x,y;
	
	N=GETi();
	GETs(str);
	
	j=0;
	FOR(i,N-1) if(str[i]==str[i+1]) j++;
	_P("%d\n",j);
	
	return;
}

B. Queue at the School

最大50文字で、男女の列がBとGで与えられる。また、時間tが与えられる。
時間が1立つと、列中でBとGが隣接し、かつBが手前にいるならBとGが入れ替わる。
時間t経過後の列の状態を答える問題。

文字列から"BG"の並びを見つけて入れ替えるだけ。
注意点として、"BBBBBG"や"BGGGGG"という並びがあっても、各人1回しか入れ替わらないので"BBBBGB""GBGGGG"となり、"GBBBBB"や"GGGGGB"にはならない。
そこで、"BG"を"GB"と入れ替えたら、次は"GB"の次の文字を見るようにした。

int N,T;
char str[100];

void solve() {
	int f,r,i,j,k,l;
	
	GET2(&N,&T);
	GETs(str);
	FOR(i,T) {
		FOR(j,N-1) if(str[j]=='B' && str[j+1]=='G'){ swap(str[j],str[j+1]); j++;}
	}
	_P("%s\n",str);
	return;
}

まとめ

本番"BBBBBG"の列が1回で"GBBBBB"となるようなコードを書いて失敗した。
簡単な問題こそミスペナルティがでかいので、慎重になりたいね。
これはTopCoderでは出てこない教訓だ。

広告を非表示にする