2013-12-15
■ SRM 600 D1H
※解いてません
問題概要
y=ax+b(0<=a 平面はいくつに分かれますか。 考えたこと ある点(p1,p2)にk本直線がのるとその点によってk-1個多く分割されると考えて良い。 ここで、ある点(p1,p2)にk本直線がのるということは b=p2-p1*aが0<=a 仮にp1>0とすると bの候補はp2,p2-p1,p2-2*p1...p2-(A-1)*p1であり、 p2-(k+a+1)*p1<0<=p2-(k+a)*p1...p2-(a+1)*p1 のような場合にk個解を持つ。 この場合だと max( (k+a)*p1,B+a*p1) <=p2< min( (k+a+1)*p1,B+(a+1)*p1)をみたせばよい。 で、このように頑張って求めたあとに数列の和の公式を適用すればおそらくO(2.4*10^3)くらいで 通るような気がしますが書けなかったのでどなたか検証していただけるとうれしいです
