C++で3つの石の山から取得できる最大の石の数を求めるアルゴリズム

3つの整数 a、b、c が与えられ、それぞれの数に対応する石の山が3つあるとします。この状態で、以下の2種類の操作を繰り返し実行できます。

• 1つ目の山から1個、2つ目の山から2個の石を取り出す(各山に十分な石が残っている場合)
• 2つ目の山から1個、3つ目の山から2個の石を取り出す(各山に十分な石が残っている場合)

このとき、合計で最大何個の石を集められるかを求めるのが本問題です。

具体例

例えば、a = 3、b = 4、c = 5 が入力として与えられた場合、出力は 9 になります。手順は以下の通りです。

1. まず「2つ目の山から1個、3つ目の山から2個」の操作を2回実行すると、2つ目の山から2個、3つ目の山から4個、合計6個の石が得られます。
2. 次に「1つ目の山から1個、2つ目の山から2個」の操作を実行すると、さらに3個の石が得られます。

合計 6 + 3 = 9 個の石を集めることができます。

解法のアプローチ

この問題を解くには、以下の手順に従います。

• まず「2つ目と3つ目の山」を使う操作に注目します。この操作で得られる石は1回あたり3個なので、実行できる回数は min(b, c / 2) です。
• 次に「1つ目と2つ目の山」を使う操作を考えます。この時点での2つ目の山の残りは b - min(b, c / 2) なので、この操作の実行回数は min(a, (b - min(b, c / 2)) / 2) となります。
• どちらの操作も1回につき3個の石を集められるため、最終的な答えは(両方の操作の合計回数)× 3 になります。

C++による実装例

以下のコードで実際の動作を確認してみましょう。

#include <bits/stdc++.h>
using namespace std;

int solve(int a, int b, int c){
    return (min(b, c / 2) + min(a, (b - min(b, c / 2)) / 2)) * 3;
}

int main(){
    int a = 3;
    int b = 4;
    int c = 5;
    cout << solve(a, b, c) << endl;
}

入力

3, 4, 5

出力

9

計算量について

この解法は条件分岐やループを使わず、min関数と四則演算のみで構成されているため、時間計算量は O(1) となります。どのような入力に対しても一定時間で答えを求められる、非常に効率的なアルゴリズムです。