kmjp's blog

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

TopCoder SRM 592 Div1 Easy LittleElephantAndBalls

SRM592に参加。まさかのEasy問題読み間違いで0完。
正答者が多かったせいでレートが冷えた…。
赤でもちょくちょく解けてない人いたし、同じ間違いした人が若干名いた模様。
逆に問題文さえわかれば300ptとは思えない簡単さな問題。
http://community.topcoder.com/stat?c=problem_statement&pm=12758

問題

RGBの3色のボールが順番に与えられる。
ここで、以下のルールで与えられたボールを順に1列に並べていく。

  • 列にボールを加えた時、ボールの左側および右側それぞれで異なる色の数だけスコアが増える

得られるスコアを最大化し、その値を答えよ。

解法

先に弁解しておくと、最初問題の見間違いをしたときは「任意の順番でボールを置いて、最終的に与えられる順番に戻す」だと思った。

で、正しい問題文の解釈に戻ると、ボールはとにかく真ん中においていき、各色1つ目のボールは左側、2個目以降は右側に置くようにすればよい。
そうすると、1つ置いた後は毎回1pt、2個目以降は2ptずつ入るようになる。

あと、以下のコードでは"R","G","B"を3で割った余りが1,2,0になることを利用している。

class LittleElephantAndBalls {
	public:
	int getNumber(string S) {
		int num[3],i,ret=0;
		ZERO(num);
		FOR(i,S.size()) {
			ret += min(2,num[0])+min(2,num[1])+min(2,num[2]);
			num[S[i]%3]++;
		}
		return ret;
	}
}

まとめ

問題解釈のミスが本当に惜しい…わかりにくいだけに例がほしかったな。
誤った解釈でもcase0同じ答えになるしな。