C++で ax²+bx+c ≥ k を満たす最小の正の整数 x を求める方法

4つの整数 a、b、c、k が与えられたとき、次の不等式を満たす最小の正の整数 x を求める問題を考えてみましょう。

ax² + bx + c ≥ k

例えば、a = 3、b = 4、c = 5、k = 6 の場合、答えは 1 になります。

解き方のアプローチ

この問題は二分探索（バイナリサーチ）の手法を使うことで効率的に解くことができます。x は最小の正の整数でなければならないため、探索範囲の下限は 0 に設定します。

関数 f(x) = ax² + bx + c は a > 0 のとき単調増加するため、二分探索が適用できます。ある x で条件を満たすなら、それより大きい x でも必ず条件を満たすからです。

サンプルコード

#include<iostream>
using namespace std;
int getMinX(int a, int b, int c, int k) {
    int x = INT8_MAX;
    if (k <= c)
       return 0;
    int right = k - c;
    int left = 0;
    while (left <= right) {
       int mid = (left + right) / 2;
       int val = (a * mid * mid) + (b * mid);
       if (val > (k - c)) {
          x = min(x, mid);
          right = mid - 1;
       }
       else if (val < (k - c))
          left = mid + 1;
       else
          return mid;
    }
    return x;
}
int main() {
    int a = 3, b = 2, c = 4, k = 15;
    cout << "Minimum value of x is: " << getMinX(a, b, c, k);
}

実行結果

Minimum value of x is: 2

コードの解説

1. 早期リターンのチェック

k が c 以下の場合、x = 0 でもすでに条件（c ≥ k）を満たしているため、即座に 0 を返します。

2. 探索範囲の設定

ax² + bx ≥ k − c を満たす最小の x を探すため、探索範囲を [0, k − c] に設定します。

3. 二分探索の実行

中央値 mid における ax² + bx の値を計算し、k − c と比較します。条件を満たす場合は答えの候補として記録し、探索範囲を左半分に狭めます。条件を満たさない場合は右半分へ移動して探索を続けます。

このアルゴリズムの計算量は O(log k) となり、1ずつ増やしながら調べる線形探索の O(k) と比べて大幅に高速です。大きな k が与えられた場合でも、実用的な時間内に答えを求めることができます。