さて、なぜかあっさり解けた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)の3点でできる三角形の領域をT[i]とする。
T[0] xor T[1] xor ... xor T[W]で得られる面積を求めよ。
解法
まず、領域を2つの対角線で区切って上下左右4つの領域に分け、それぞれを順に考える。
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が奇数なら足し、偶数なら引く。
最後に4つに区切った領域の下の部分(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数はさほど多くないんだよな…。
今回日本勢が強かったらしいけど、こういうの日本で中学受験や高校受験でよくやるからかな?