C++で指定範囲のコストと数量から比率rが取得できるか判定する方法

概要

コストの範囲(lowCost 以上 upCost 以下)と数量の範囲(lowQuant 以上 upQuant 以下)が与えられたとき、r = cost ÷ quantity を満たす指定された比率 r を実現できるかどうかを判定するのが本記事のテーマです。

入出力例

例1

lowCost = 2, upCost = 10
lowQuant = 3, upQuant = 9
r = 3

出力:

Yes

解説: cost = r × quantity = 3 × 3 = 9 となり、cost は [2, 10]、quantity は [3, 9] のいずれの範囲内にも収まるため、「Yes」が返ります。

例2

lowCost = 15, upCost = 31
lowQuant = 6, upQuant = 13
r = 8

出力:

No

解説: 数量が最小の 6 でも cost = 8 × 6 = 48 となり、これはコスト範囲 [15, 31] を超えてしまいます。数量を増やすほど cost は大きくなる一方のため、条件を満たす組合せは存在せず、「No」が返ります。

解法の考え方

比率の定義から、次の関係式が導けます。

cost = quantity × r

ここで r はコストと数量の比です。この式をもとに、数量の範囲内の各値について「その値 × r」を計算し、結果が lowCost 以上 upCost 以下に収まるものが1つでも見つかれば答えは「Yes」、1つもなければ「No」になります。

C++での実装例

数量の範囲を線形に走査するシンプルな実装は以下の通りです。

// 指定されたコスト・数量の範囲から
// 比率 r が取得可能かどうかを調べる C++ プログラム
#include <bits/stdc++.h>
using namespace std;

// 与えられたコスト範囲・数量範囲から
// 比率 r が実現可能なら true を返す
bool isRatioPossible(int lowCost, int upCost,
                     int lowQuant, int upQuant,
                     int r) {
    // 数量の範囲内の値をすべて試す
    for (int i = lowQuant; i <= upQuant; i++) {
        // 数量 i に対応するコストを計算
        int ans = i * r;
        // コストが指定範囲内に収まれば成功
        if (lowCost <= ans && ans <= upCost)
            return true;
    }
    return false;
}

// 動作確認用コード
int main() {
    int lowCost = 2, upCost = 10;
    int lowQuant = 3, upQuant = 9;
    int r = 3;

    if (isRatioPossible(lowCost, upCost,
                        lowQuant, upQuant, r))
        cout << "Yes";
    else
        cout << "No";
    return 0;
}

出力:

Yes

計算量

• 時間計算量: O(upQuant − lowQuant + 1) — 数量の範囲のサイズに比例
• 空間計算量: O(1)

応用: O(1) で判定する最適化

数量の範囲が非常に大きい場合は、全探索ではなく数学的に判定すると効率的です。cost = quantity × r より、lowCost 以上になる最小のコストを作る数量は ⌈lowCost ÷ r⌉ です。この数量が [lowQuant, upQuant] の範囲に入り、かつ対応するコストが upCost 以下であれば「Yes」です。

// 正の整数を前提とした O(1) 判定
bool isRatioPossibleFast(int lowCost, int upCost,
                         int lowQuant, int upQuant,
                         int r) {
    // lowCost 以上になる最小の cost = q * r を作る数量 q
    int q = (lowCost + r - 1) / r;  // ceil(lowCost / r)
    q = max(q, lowQuant);           // 数量の下限も満たす
    return q <= upQuant && (long long)q * r <= upCost;
}

この方法なら数量の範囲がどれだけ広くても、定数時間で答えを求められます。

まとめ

「cost = quantity × r」という関係式を利用すれば、指定範囲内で比率 r が実現可能かどうかは簡単に判定できます。まずは分かりやすい線形探索で実装し、パフォーマンスが必要になったら O(1) の数式ベースの判定に置き換えるのが良いアプローチです。