C++で美しい装飾に使える飾りの最大数を求める方法

問題概要

3つの整数 y、b、r が与えられます。装飾用の飾りとして、黄色い飾りが y 個、青い飾りが b 個、赤い飾りが r 個あります。

使用する青い飾りの数が黄色い飾りの数よりちょうど1個多く、赤い飾りの数が青い飾りの数よりちょうど1個多い場合、その装飾は「美しい」とみなされます。できるだけ多くの飾りを使いたい一方で、装飾も美しく仕上げたいと考えています。このとき、美しい装飾に使用できる飾りの最大数を求めるのが本問題の目的です。

たとえば、入力が y = 8、b = 13、r = 9 の場合、出力は 24 になります。これは黄色7個・青8個・赤9個を使用すると 7 + 8 + 9 = 24 となり、これが条件を満たす最大の組み合わせだからです。

解法の考え方

黄色い飾りを k 個使用すると仮定すると、「美しい装飾」の条件から以下の関係が導かれます。

• 青い飾りは k + 1 個必要 → b ≥ k + 1 が成り立つこと
• 赤い飾りは k + 2 個必要 → r ≥ k + 2 が成り立つこと

したがって、k は「y」「b − 1」「r − 2」のうち最小値以下でなければなりません。使用する飾りの合計は k + (k + 1) + (k + 2) = 3k + 3 となるため、答えは次の式で一発に求められます。

return 3 * min(y, min(b - 1, r - 2)) + 3;

C++での実装例

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

#include <bits/stdc++.h>
using namespace std;
int solve(int y, int b, int r){
    return 3 * min(y, min(b - 1, r - 2)) + 3;
}
int main(){
    int y = 8;
    int b = 13;
    int r = 9;
    cout << solve(y, b, r) << endl;
}

入力

8, 13, 9

出力

24

計算量

このアルゴリズムは数値の比較のみで構成されており、ループや再帰を一切使いません。そのため時間計算量は O(1)、追加のメモリ消費もゼロで、非常に効率的な解法といえます。