C++で指定された範囲からパックサイズを判定するコードの書き方

問題の概要

2つの整数 l と r が与えられているとします。ある店では、食品を a 個ずつまとめたパックを割引価格で販売しており、ある顧客は x 個の食品を購入したいと考えています。この顧客は次のような貪欲な戦略に従って行動します。

• まず、x / a の切り捨て値に相当する数だけパックを割引価格で購入します。
• その後、残りの x mod a 個の食品を1個ずつ個別に購入しようとします。

しかし、顧客は貪欲なので、残りを1個ずつ買おうとしたとき、その数（x mod a）が a / 2 以上になると、1個ずつ買うよりもパック全体をまとめて購入した方が得だと判断し、結局パックごと買ってしまいます。

顧客は l から r まで（両端を含む）の任意の個数の食品を購入できます。ここでの課題は、すべての顧客が当初予定していたよりも多くの缶を購入する結果になるようなパックサイズ a を選べるかどうかを判定することです。

例えば、入力が l = 3、r = 4 の場合、出力は True になります。なぜなら、a = 5 とすれば、顧客が3個または4個の缶を購入したい場合でも、残りが a / 2 以上になるため、パック1つを丸ごと購入することになるからです。

解法のアプローチ

この問題を解くには、以下のシンプルな手順に従います。

r / 2 >= l の場合：
    false を返す
それ以外の場合：
    true を返す

ロジックの解説

この判定ロジックのポイントは、r / 2 と l の大小関係にあります。もし r / 2 >= l が成り立つ場合、範囲内の一部の値 x に対しては、どのようなパックサイズ a を選んでも顧客が余分に購入することを保証できません。逆に r / 2 < l であれば、適切なパックサイズを選ぶことで、範囲内のすべての購入希望数に対して、顧客に当初の希望数より多く購入させることが可能になります。

実装例

理解を深めるために、以下のC++による実装例を見てみましょう。

#include <bits/stdc++.h>
using namespace std;
bool solve(int l, int r){
    if (r / 2 >= l)
        return false;
    else
        return true;
}
int main(){
    int l = 3;
    int r = 4;
    cout << solve(l, r) << endl;
}

入力

3,4

出力

1

出力が 1（true）となっており、l = 3、r = 4 の範囲では条件を満たすパックサイズが存在することが確認できます。