Pythonで指定範囲のコストと数量から特定の比率が存在するか判定する方法

問題の概要

コストの範囲（lowCost〜upCost）と数量の範囲（lowQuant〜upQuant）が与えられたとき、r ＝ コスト ÷ 数量 となる指定の比率 r を見つけられるかどうかを判定する問題です。ここで、コストは lowCost ≤ cost ≤ upCost の範囲内、数量は lowQuant ≤ quantity ≤ upQuant の範囲内に収まっている必要があります。

例えば、lowCost = 2、upCost = 10、lowQuant = 3、upQuant = 9、r = 3 という入力の場合、出力は True になります。なぜなら、コスト = r × 数量 = 3 × 3 = 9 と計算でき、このコスト 9 は範囲 [2, 10] 内に、数量 3 は範囲 [3, 9] 内にそれぞれ収まるためです。

解決のアプローチ

この問題は、次の手順で解くことができます。

• 数量の範囲（l_quant〜u_quant）の各値 i について順に処理を行います。
• res = i × ratio を計算します。
• res が l_cost 以上かつ u_cost 以下であれば、条件を満たす組み合わせが存在するので True を返します。
• すべての値を確認しても条件を満たすものが見つからなければ、False を返します。

実装例

以下は、上記の考え方をPythonで実装した例です。

def can_we_find_r(l_cost, u_cost, l_quant, u_quant, ratio) :
   for i in range(l_quant, u_quant + 1) :
      res = i * ratio
      if (l_cost <= res and res <= u_cost) :
         return True
   return False

l_cost = 2
u_cost = 10
l_quant = 3
u_quant = 9
ratio = 3

print(can_we_find_r(l_cost, u_cost,l_quant,u_quant, ratio))

入力

2, 10, 3, 9, 3

出力

True

計算量の目安

この線形探索ベースのアプローチでは、数量の範囲の幅を n とすると、時間計算量は O(n)、使用する追加メモリは定数なので空間計算量は O(1) となります。

より効率的なO(1)の方法

範囲が非常に大きい場合は、ループを使わず数学的に判定することもできます。比率 r に対して「コスト範囲に対応する数量の候補」は、ceil(l_cost / ratio) から floor(u_cost / ratio) までの整数として求められます。この候補区間が与えられた数量範囲と重なるかどうかを確認すればよいのです。

import math

def can_we_find_r_fast(l_cost, u_cost, l_quant, u_quant, ratio) :
   q_min = math.ceil(l_cost / ratio)
   q_max = math.floor(u_cost / ratio)
   # 数量の候補区間と指定された数量範囲の共通部分を確認
   return max(q_min, l_quant) <= min(q_max, u_quant)

print(can_we_find_r_fast(2, 10, 3, 9, 3))  # True

この方法なら、範囲の大きさに関係なく一定時間で判定できるため、大きな数値範囲を扱う場合に特に有効です。