TopCoder, SRM 635, Division 2, Level 2 : QuadraticLaw

問題文

　http://community.topcoder.com/stat?c=problem_statement&pm=13486&rd=16078

問題概要

　ある教師は、授業に 分遅刻したら、授業を 分早く終わらせることにしている。授業が始まる前に授業を終わらせることはできないため、遅刻しすぎることはできない。なお、授業開始後直ちに授業を終わらせることは許される。
　正整数 が与えられる。授業時間が 分確保されているとき、この教師は最大で何分遅刻することができるか、求めよ。
　

解法

　遅刻時間 分に対し、授業時間が 分消費されます。これが 分を超えてはいけないということなので、問題は「 を満たす最大の を求めよ」と言い換えられます。
　式やサンプル入出力から、答えは の周辺だろうという検討が付きますが、　として左辺を計算すると最大で だけ をオーバーしてしまいます。ところで、不等式の左辺を変形すると となります。また、ある に対して、 を 1 減らした場合の値は となるので、 だけ値が小さくなることが分かります。 とした場合の超過分は最大で であったので、オーバーしていたら を 1 小さくすることで不等式を満たすようになります。従って、これで問題を解けます。

コード

using LL = long long;

class QuadraticLaw
{
public:
	long long getTime( long long d )
	{
		LL t = sqrt( d );
		return t - ( d < t * t + t );
	}
};