Official

B - Setsubun Editorial by physics0523


for ループを用いて、 \(i\) 年後に \(N+i\) 個の豆を食べることをシミュレーションすることでこの問題に正解できます。

実装例 (C++):

#include<bits/stdc++.h>

using namespace std;

int main(){
  int n,k;
  cin >> n >> k;
  for(int i=0;;i++){
    k-=(n+i);
    if(k<=0){
      cout << i << "\n";
      break;
    }
  }
  return 0;
}

では、この解法が成立するのは一体なぜでしょうか?

この問題の制約は \(1 \le N,K \le 10^8\) です。
なので、 \(1\) 歳から始めて \(10^8\) 個以上の豆を食べるまでが最も年数がかかるケースです。
一方、 \(1\) 歳から始めて \(10^5\) 年間豆を食べ続けた時、食べる豆の個数は約 \(5 \times 10^9\) 個となります。
よって、 \(K\) 個以上の豆を食べるということは必ず \(10^5\) 年後までに訪れることになります。
ループを \(10^5\) 回回すということは、プログラムを実行すれば実行時間制限の 2 秒 に対して十分高速に実現可能です。

posted:
last update: