moistx https://blog.hatena.ne.jp/moistx/ Logfiles https://logfiles.hatenablog.com/ SRM 問題文 本来の授業時間 d が与えられる。授業の開始を t 遅らせるとき、更に t^2 の時間だけ授業時間が少なくなる。授業時間をできるだけ少なくするための t を求めよ。解説 入力が10^18なので普通に線形探索は不可。二分探索しても良いが、整数型で探索範囲は削れる。方法はいくつか有るようだが、一つの例として√を整数切り捨てで計算したとき t の値が √(d+1) * √(d+1) 以上にはならないことを利用すると探索範囲を大幅に削ることが出来る。そこから線形探索で t の値をデクリメントしながら整数切り捨ての計算で二乗が d と一致したときの t の値がちょうど答え。解はすぐ見つかる。以下… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Flogfiles.hatenablog.com%2Fentry%2F20141005%2F1412466132" title="SRM635 Div2Med QuadraticLaw - Logfiles" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2014-10-05 08:42:12 rich https://logfiles.hatenablog.com/entry/20141005/1412466132 1.0 100%