Official

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: