torus711 のアレ

主に競技プログラミングの問題について書きます

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

問題概要

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

解法

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

コード

using LL = long long;

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