ABC206 B 解答

B - Savings（14）

問題

B - Savings

問題文

シカのAtCoDeerくんは、空の貯金箱を持っています。
AtCoDeerくんは、その貯金箱に、1 日目の朝に 1 円、2 日目の朝に 2 円 … というように、i 日目の朝に i 円を貯金箱に入れます。
また、AtCoDeerくんは、毎日夜に貯金箱にいくら入っているかを確認します。AtCoDeerくんが貯金箱に N 円以上入っていることを初めて確認するのは、何日目の夜でしょうか?

制約

1 ≤ N ≤ 10^9
N は整数

考察

貯金をしていきます。本問題は「二分探索」や「式変形する」などいろいろな方法が考えられますが、シンプルな方法で解いていきましょう。

愚直に1日目から貯金していきましょう。

sum=0

という貯金箱に1日目には1円、2日目には2円を入れていきます。毎日これを続けていき、N円をはじめて超えた(到達した)日にちを出力してあげれば答えです。

このように、解法自体はとってもシンプルです。しかし、大切なのはここからです。この方法で計算時間が間に合うかどうかを判断する必要があります。

1日目には1円、2日目には2円、...ですので、入れるお金は次のような等差数列になります。

1 2 3 4 5 6 ...

この等差数列の1項目からK項目(1~K)までの和は次の式で表されます。

K * (K + 1) / 2

です。ここで、K^2が登場しますね。だいたい、K日目まで貯金するとK^2円を貯めることができます。

さて本問題の制約はN≦10^9でした。ここまで貯金するのには2乗してこの値になる日数が必要となります。ということで、すごくざっくり言いますと

10^5

程度の日数があれば十分目標を達成できます。10^5なら1日ずつ計算しても間に合いそうです。

以上により愚直に計算しても大丈夫なことが分かりました。ということで実装しましょう。

実装

 #include <bits/stdc++.h> #define  rep(i,n) for(int i=0;i<n;++i) #define  reps(i,s,n) for(int i=s;i<n;++i)
using namespace std;
using ll = long long;
using P = pair<int, int>;
using T = tuple<int, int, int>;

int main()
{
   int n;
   cin >> n;
   int sum = 0;
   rep(i, n)
   {
       sum += i + 1;
       if (sum >= n)
       {
           cout << i + 1 << endl;
           break;
       }
   }

   return 0;
}

あとがき

本問題は答えを求めることよりも計算量(厳密ではないですが、どのくらいの計算回数が必要か)を考えることが非常に重要だと思います。だいたいABCのB問題では計算量を気にしになくても解けるようになっていますが、意識するとしないでは、大きく違います。またC問題では愚直に書けば答えは出るけど間に合わない！という問題がよく問われますので、易しい問題のときから、

どのくらい計算しなきゃいけないんだろう

と考える癖をつけると良いと思います。