C++で材料を無駄なく使い切るハンバーガーの個数を求める方法

問題の概要

2つの整数 tomatoSlices（トマトのスライス数）と cheeseSlices（チーズのスライス数）が与えられます。これらは、次の2種類のバーガーを作るための材料です。

• ジャンボバーガー： トマトのスライス4枚とチーズのスライス1枚を使用
• スモールバーガー： トマトのスライス2枚とチーズのスライス1枚を使用

与えられた材料をすべて使い切り、トマトのスライスとチーズのスライスの残りがどちらも0になるように、ジャンボバーガーとスモールバーガーの個数 [total_jumbo, total_small] を求めます。もし材料を余らせずに使い切ることが不可能な場合は、空の配列 [] を返します。

例として、tomatoSlices = 16、cheeseSlices = 7 が入力された場合、出力は [1, 6] になります。これは、ジャンボバーガー1個とスモールバーガー6個を作ると、トマトのスライスが 4×1 + 2×6 = 16 枚、チーズのスライスが 1 + 6 = 7 枚となり、すべての材料をちょうど使い切れることを示しています。

解法のアプローチ

この問題は、連立一次方程式として捉えることができます。ジャンボバーガーの個数を j、スモールバーガーの個数を s とすると、次の2式が成り立ちます。

• 4j + 2s = tomatoSlices
• j + s = cheeseSlices

この方程式を解くために、以下の手順に従います。

1. 結果を格納するための配列 ans を用意します。
2. トマトのスライス数が奇数、または cheese > tomato/2、または tomato > 4×cheese のいずれかに該当する場合は、材料をちょうど使い切ることが不可能なため、空の ans をそのまま返します。
3. x := (4 × cheese − tomato) / 2 を計算します（スモールバーガーの個数）。
4. y := (tomato − 2×x) / 4 を計算します（ジャンボバーガーの個数）。
5. y、x の順に ans に挿入します。
6. ans を返します。

条件チェックの理由

なぜこれらの条件で不可能性を判定できるのでしょうか。理由は次のとおりです。

• 必要なトマトのスライス数は 4j + 2s = 2(2j + s) と表せるため、必ず偶数でなければなりません。
• トマトの必要枚数の半分は 2j + s、チーズの必要枚数は j + s なので、cheese ≤ tomato/2 が成立する必要があります。
• トマトのスライス数は最大でも 4(j + s) = 4×cheese 枚であるため、tomato ≤ 4×cheese が成立する必要があります。

これらの条件をすべて満たしていれば、解は必ず一意に存在することが保証されます。

C++による実装例

それでは、理解を深めるために実際の実装を見てみましょう。

例

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
   cout << "[";
   for(int i = 0; i<v.size(); i++){
      cout << v[i] << ", ";
   }
   cout << "]"<<endl;
}
class Solution {
   public:
   vector<int> numOfBurgers(int t, int c) {
      vector <int> ans;
      if(t % 2 != 0 || c > t/2 || t > c*4)return ans;
      int x = (4 * c - t) / 2;
      int y = ( t - (2 * x) )/ 4;
      ans.push_back(y);
      ans.push_back(x);
      return ans;
   }
};
main(){
   Solution ob;
   print_vector(ob.numOfBurgers(16,7));
}

入力

16
7

出力

[1, 6]

このように、連立方程式を立てて条件判定を行うことで、与えられた材料から無駄なく作れるバーガーの組み合わせを、O(1) の計算量で効率的に求めることができます。