C++で解く：パーティーの全員が好きなアイスクリームを受け取れるか判定する方法

あるパーティーに、性質の異なる3つのグループの人々が参加するとします。

1つ目のグループ： バタースコッチ味のアイスクリームしか好まず、他の味は一切食べません。
2つ目のグループ： ストロベリー味だけが苦手で、それ以外の味はすべて好きです。
3つ目のグループ： どんな味のアイスクリームでも喜んで食べます。

ここで、1つ目のグループから x 人、2つ目のグループから y 人、3つ目のグループから z 人がパーティーに参加し、参加者全員が少なくとも1個は自分の好きなアイスクリームを受け取れなければなりません。一方、主催者が用意したアイスクリームは、バタースコッチ味が a 個、チョコレート味が b 個、ストロベリー味が c 個です。このとき、全員が満足できる配布が可能かどうかを判定するのが本問題の目的です。

例えば、a = 6、b = 5、c = 5、x = 3、y = 8、z = 4 という入力が与えられた場合、出力は「Possible（可能）」となります。

考え方と解法の手順

この問題のポイントは、選択の自由度が最も低いグループから順番に確認していくことです。1つ目のグループはバタースコッチ味しか食べられないため、まず「a ≥ x」が必須条件となります。さらに、1つ目と2つ目のグループはどちらもストロベリー味を食べられない（または食べたくない）ため、「a + b ≥ x + y」が成り立つ必要があります。最後に、全員分の総数を見て「a + b + c ≥ x + y + z」であれば、全体としての個数も足りていることになります。この3つの条件がすべて満たされれば「Possible」、一つでも満たされなければ「Not Possible」と判定できます。

擬似コードで表すと以下のようになります。

if a < x or a + b < x + y or a + b + c < x + y + z, then:
    print("Not Possible.")
Otherwise
    print("Possible.")

C++による実装例

理解を深めるために、実際のC++コードを見てみましょう。

#include <bits/stdc++.h>
using namespace std;
#define N 100
void solve(int a, int b, int c, int x, int y, int z) {
    if (a < x || a + b < x + y || a + b + c < x + y + z)
        cout<<"Not Possible.";
    else
        cout<<"Possible.";
}
int main() {
    int a = 6, b = 5, c = 5, x = 3, y = 8, z = 4;
    solve(a, b, c, x, y, z);
    return 0;
}

入力例

6, 5, 5, 3, 8, 4

出力例

Possible.

このアルゴリズムは単純な比較演算のみで構成されているため、計算量は O(1) となり、非常に効率的です。累積和の考え方を使って、制約の厳しいグループから順に在庫を割り当てていく発想は、類似の貪欲法（グリーディ法）の問題にも応用できる有用なテクニックです。