SRM472

250/500は簡単。
1000はランダムウォークの問題。メモリや計算時間を考慮すると、難解。というか解き方分からないよ…。

250/ColorfulTilesEasy

1列に赤・緑・青・緑のいずれかの色のついたタイルが並んでいる。
隣あったタイルが同じ色とならないようにするには、何枚のタイルの色を塗り替える必要があるか。

class ColorfulTilesEasy {

	public: int theMin(string room) {
		int count = 0;
		for(unsigned int i=1; i<room.size(); i++){
			if(room[i] == room[i-1]){
				count++;
				i++;
			}
		}
		return count;
	}

};

特に難しいところもなし。

500/PotatoGame

ある数値が始めに与えられる。太郎と花子が順番に4の累乗の中で任意の数字を、0未満にならないように始めに与えられた数値から引いていく。
与えられた数値を0に出来るのは太郎か花子か。

class PotatoGame {

public:
	string theWinner(int n) {
		int div = n;
		int validnum = 1;
		int turns = 0;
		while(div != 0){
			if( div % (validnum*4) == 0){
				validnum = validnum * 4;
			}else{
				div -= validnum;
				turns++;
			}
		}

		string result;
		if(turns % 2 == 1){
			result = "Taro";
		}else{
			result = "Hanako";
		}

		return result;
	}

};

結構撃墜された人が多かったみたい。
テストデータがあまりに簡単すぎたせいなのかな。

追記：System Testで弾かれてるｗｗ
optimalに動くことをそもそも考えてなかった…。
ミスったなー。
mod5を考えればすぐに解が出ます。