TopCoder SRM 642 Div2 Medium LightSwitchingPuzzle

SRM642は不参加。
Div1 Easyがさっくり解けたと思ったらコーナーケースで落としてたので、結果的に出なくてよかったことに。
http://community.topcoder.com/stat?c=problem_statement&pm=13555

問題

N個の電球が１列に並んでおり、それぞれのon/offが与えられる。
i番目の電球に対応するボタンを押すと、iの整数倍の位置に相当する電球のon/offが反転する。

全部の電球をoffにするには、最小何個のボタンを押す必要があるか。

解法

i番目のボタンを押すとi番目以降の電球の状態が変化する。
逆にボタンの位置より手前の電球の状態は変化しない。

よって、番号の小さい順位にonのところのボタンを押す、という処理を繰り返せばよい。

class LightSwitchingPuzzle {
	public:
	char S[1020];
	int minFlips(string state) {
		int i,l=state.size();
		FOR(i,l) S[i]=state[i]=='Y';
		
		int x=0,y;
		FOR(i,l) if(S[i]) {
			x++;
			for(y=i;y<l;y+=i+1) S[y]^=1;
		}
		return x;
		
	}
}

まとめ

もっとNが大きくても大丈夫だね。