B - Savings Editorial by physics0523
まず、答えの最大値を見積もります。
今回の問題では、 \(N \le 10^9\) です。明らかに、答えは \(10^9\) 以下ですが、本当にこのくらい答えが大きくなってしまうでしょうか?
少し考えると、 例えば、 \(1000\) 日目以降は少なくとも毎日 \(1000\) 円以上貯金額が増え続けることが分かります。なので、このペースで \(10^9\) 円に到達するのは、どれだけ遅くとも \(10^6+1000\) 日後であることがわかります。
この程度の日数であれば、forループによるシミュレーションを \(1\) 日ごとに実行しても余裕をもって実行時間制限に間に合います。
なお、実装の方針としては、 while(1) のような無限ループの形でプログラムを記述し、貯金額が \(N\) 円以上になったタイミングで即座にループを抜け出す、というような方針をとるとより簡潔です。実装例も参照してください。
Octaveによる実装例:
n = scanf('%d', 'C');
i = 1;
money = 0;
while 1
money += i;
if money >= n
break;
end
i++;
end
printf('%d\n',i);
PHPによる実装例:
<?php
$n = fgets(STDIN);
for($i = 1 ; ; $i++){
$n -= $i;
if($n <= 0){
printf("%d\n",$i);
break;
}
}
?>
BONUS! \(N \le 10^{18}\) で今回の問題を解いてみましょう。
ヒント
実は、 \(N\) 日目時点での貯金額は \(\frac{(N+1) \times N}{2}\) 円となります。
解法
\(X<Y\) の時、 \(X\) 日目時点の貯金額より \(Y\) 日目の貯金額の方が必ず大きくなります。
よって、「答えが \(X\) より大きいか?」という形の二分探索をすることによって解くことができます。
Goによる実装例:
package main
import "fmt"
func f(n int64) int64 {
return (n*(n+1))/2
}
func main() {
var n,ng,ok,mid int64
fmt.Scan(&n)
ng = 0
ok = 3000000000
for (ok - ng) > 1 {
mid = (ok + ng) / 2
if f(mid) < n {
ng = mid
} else {
ok = mid
}
}
fmt.Println(ok)
}
posted:
last update: