TopCoder SRM 587 Div1 Medium TriangleXor

さて、なぜかあっさり解けた550ptのMedium。
ほぼfirst answerと同じ速度で解けている…。
なんてこった、なぜこんな回に出られなかった…。
http://community.topcoder.com/stat?c=problem_statement&pm=12528

問題

幅Wが与えられたとき、高さ1・幅Wの領域を考える。
各i(0～W)につき、(0,1)(W,1)(i,0)の３点でできる三角形の領域をT[i]とする。
T[0] xor T[1] xor ... xor T[W]で得られる面積を求めよ。

解法

まず、領域を２つの対角線で区切って上下左右４つの領域に分け、それぞれを順に考える。

Wが偶数のとき、上・左・右の領域の和の面積をまず3W/4カウントする。
次に左側と右側をカウントする。
左側を考えると、(0,0)-(W,1)に伸びる対角線と(0,1)-(i,0)を結ぶ線の交点は、(0,0)-(W,1)の線をi:Wに区切る線なのでそのX座標はW*i/(i+W)
よって左側の領域から(W*i/(i+W))、右側の領域からも同じ量の面積を、iが奇数なら足し、偶数なら引く。

最後に４つに区切った領域の下の部分(W/2,1/2)-(0,0)-(W,0)で囲まれた部分を求める。
高さ1/2W、2/2W、3/2W、…(W-1)/Wのところに線を引くと、簡単な図形ができる。
例えば例題のW=6のケースで高さ1/2Wのところに線を引くと、底辺の長さ1、高さ1/2の下向きの色塗られた三角形が5個、上向きの黒い三角形が6個見えるので、5/4分の面積を加算する。
同様に各段の三角形の面積を足していけばよい。

class TriangleXor {
	public:
	int theArea(int W) {
		double S=0;
		int i;
		
		if(W%2==0) S=W*0.75;
		for(i=W;i>=1;i--) {
			if(i%2==0) S-=(double)W*i/(i+W);
			else S+=(double)W*i/(i+W);
		}
		
		FOR(i,W) {
			if(i%2==0) S+=(W-i)/(double)(4*W);
			else S+=(W-i-1)/(double)(4*W);
		}
		
		return (int)S;
	}
};

まとめ

550ptにしては妙に簡単な問題。
でもSubmit数はさほど多くないんだよな…。
今回日本勢が強かったらしいけど、こういうの日本で中学受験や高校受験でよくやるからかな？