TopCoder SRM 635 Div2 Medium QuadraticLaw

Div2にしても簡単？
http://community.topcoder.com/stat?c=problem_statement&pm=13412

問題

授業時間がDある。
先生はT遅れてきてT*T早く授業を終えた。

このようなことが可能な最大の整数Tを求めよ。

解法

T^2+T=T*(T+1)≦Dとなる最大のTを求める。
２次方程式でもよいし、以下のように二分探索でも良い。

class QuadraticLaw {
	public:
	long long getTime(long long d) {
		ll c=0;
		for(int i=30;i>=0;i--) if((c+(1<<i))*(c+(1<<i)+1)<=d) c|=1<<i;
		return c;
	}
}

まとめ

ずいぶんあっさり。