C++で必要なドリンク詰め替えパックの数を計算する方法

ある週にスタジアムで「a」回の試合と「b」回の記者会見が開催されるとします。スタジアムにはカフェテリアが2つあり、1つは選手用ロッカールーム内に、もう1つは記者会見エリアに設置されています。各カフェテリアにはソフトドリンクディスペンサーがあり、週の初めに補充しておく必要があります。

ロッカールームのディスペンサーは使用頻度が非常に高いため、「c」試合ごとに補充が必要です。一方、会見エリアのディスペンサーは「d」イベントごとに補充が必要です。スタジアム管理委員会は各週の初めに合計「k」個の詰め替えパックを発注でき、ロッカールーム用に「x」個、会見室用に「y」個を割り当てます。ただし、x + y <= k という制約があります。

試合スケジュールが与えられたとき、x と y の値を求めます。必要な詰め替えパックの合計が k を超える場合は「Limit Exceeded」と出力してください。

例えば、入力が a = 8、b = 8、c = 4、d = 6、k = 9 の場合、出力は「2 2」になります。これは、試合8回を4試合ごとの補充で割ると2回、記者会見8回を6イベントごとの補充で割ると切り上げで2回必要となり、合計4個が上限9個以内に収まるためです。

解法のアプローチ

この問題は、切り上げ除算（天井関数）を使うことで簡単に解くことができます。以下の手順に従います。

• ロッカールーム用に必要な補充回数を計算します：a = (c + a - 1) / c（これは a を c で割った切り上げ値と同じ）
• 会見室用に必要な補充回数を計算します：b = (d + b - 1) / d
• a + b <= k であれば、a と b の値を出力します
• それ以外の場合は「Limit Exceeded」を出力します

ポイントは、(c + a - 1) / c という式です。整数除算では小数点以下が切り捨てられるため、分子に (除数 - 1) を加えることで切り上げ除算を実現しています。これにより、端数が発生した場合でも余分な1回分の補充を正しくカウントできます。

実装例

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

#include <bits/stdc++.h>
using namespace std;
#define N 100
void solve(int a, int b, int c, int d, int k) {
    a = (c + a - 1) / c;
    b = (d + b - 1) / d;
    if(a + b <= k)
        cout<<a<<" "<<b<<"\n";
    else
        cout<<"Limit Exceeded."<<"\n";
}
int main() {
    int a = 8, b = 8, c = 4, d = 6, k = 9;
    solve(a, b, c, d, k);
    return 0;
}

入力

8, 8, 4, 6, 9

出力

2 2

このように、切り上げ除算を活用することで、必要な補充回数を効率的に計算し、発注上限との比較も簡単に行えます。計算量は O(1) と定数時間で済むため、非常に効率的なアルゴリズムです。