【AtCoder】ABC 443 B - Setsubun

2026-02-01

AtCoder/ABC/B問題 AtCoder/ABC/200点問題 AtCoder/灰Diff AtCoder/NoviSteps/6Q AtCoder/二分探索/めぐる式二分探索 AtCoder/シミュレーション競技プログラミング

B - Setsubun

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

実行時間制限: 2 sec / メモリ制限: 1024 MiB / Difficulty: 28 / NoviSteps: 6Q / 配点: 200 点

問題概要

高橋君は、年に $1$ 度の節分には年齢と同じ数の豆を食べる。高橋君は、今年の節分の時点で $N$ 歳である。

高橋君が今年以降で累計 $K$ 個以上の豆を食べたことになるのは、最短で何年後の節分か求めよ。

制約

$1 \le N,K \le 10^8$
入力は全て整数

考察

二分探索で解く

答えが $X$ 年後であるとすると, 次の不等式が成り立つ。

\begin{align*} \sum_{i=0}^{X} (N + i) & \geq K \\ \iff \dfrac{\left\{ N + (N+X) \right\} (X + 1)}{2} & \geq K \tag{1} \end{align*}

左辺は $X$ の2次関数であるため、 $X$ の正領域で単調である。

したがって、二分探索でこれを満たす最小の $X$ を求めればよい。

もっと簡単にシミュレーションで解く

一見すると愚直なシミュレーションでは間に合わないように思える。

しかし、最悪なケース $(N=1, K=10^8)$ において、式 $(1)$ にこれを代入すると、

\begin{align*} \dfrac{\left\{ 1 + (1+X) \right\} (X + 1)}{2} & \geq 10^8 \\ \iff (X + 2)(X + 1) & \geq 2 \times 10^8 \end{align*}

となり、少なくとも $X =10^5$ 程度で条件を満たすことが分かる。

したがって、ループ文で単純にシミュレーションすれば十分間に合うのである。

実装例

二分探索で解く

いつもの「めぐる式二分探索」を用いると簡単だろう。

1.#include <bits/stdc++.h>
2.using namespace std;
3. 
4.constexpr int INF = 1e+9;
5. 
6.using ll = long long;
7. 
8.// ======================================== //
9. 
10.int main()
11.{
12.    ll N, K;
13.    cin >> N >> K;
14. 
15.    ll ok = INF, ng = -1;
16.    while (abs(ok - ng) > 1)
17.    {
18.        ll mid = ng + (ok - ng) / 2;
19. 
20.        if ((N + (N + mid)) * (mid + 1) / 2 >= K)
21.            ok = mid;
22.        else
23.            ng = mid;
24.    }
25. 
26.    cout << ok << endl;
27.    return 0;
28.}

Submission #72872607 - Denso Create Programming Contest 2026（AtCoder Beginner Contest 443）

Submission #72872607 - Denso Create Programming Contest 2026（AtCoder Beginner Contest 443）

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

シミュレーションで解く

1.#include <bits/stdc++.h>
2.using namespace std;
3. 
4.// ======================================== //
5. 
6.int main()
7.{
8.    int N, K;
9.    cin >> N >> K;
10. 
11.    int years = 0, sum = 0;
12.    while (sum < K)
13.    {
14.        sum += N + years;
15.        years++;
16.    }
17. 
18.    cout << years - 1 << endl;
19. 
20.    return 0;
21.}

Submission #72932301 - Denso Create Programming Contest 2026（AtCoder Beginner Contest 443）

Submission #72932301 - Denso Create Programming Contest 2026（AtCoder Beginner Contest 443）

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

実装時間: 5 分

コメント

二分探索を考えたせいで逆に時間がかかってしまった。