水注ぎゲームで全員が勝者になるかを判定するC++コード

n個の要素を持つ配列Aと、数値sが与えられます。テーブルの上には、空のコップが1つと、水の入ったコップがn個置かれています。このゲームには複数のプレイヤーが参加し、各ターンでプレイヤーは水の入ったコップを1つ選び、その水をすべて空のコップに注ぎます。コップがあふれてしまった場合、そのプレイヤーは負けとなります。ここで、すべてのプレイヤーが勝者になれるかどうか(コップがあふれないかどうか)を判定する必要があります。なお、コップがすでに満杯になっている場合、次のプレイヤーは自分のターンを行いません。sは空のコップの容量を、A[i]はi番目のコップに入っている水の量を表します。

例えば、入力がA = [3, 1, 3]、s = 4である場合、出力はTrueになります。1番目と2番目のプレイヤーが水を注ぐとコップがちょうど満杯になり、最後のプレイヤーはターンを行わないためです。

解法の手順

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

k := 0
n := Aのサイズ
配列Aをソートする
i := 0 で初期化し、i < n - 1 の間、i を 1 ずつ増やしながら以下を繰り返す:
    k := k + A[i]
k > s の場合:
    false を返す
それ以外の場合:
    true を返す

アプローチのポイント

配列をソートした後、最も水量の多いコップを除いた残りのn-1個のコップに入っている水の合計を求めます。この合計が容量s以下であれば、途中でコップがあふれることなく水を注ぐことができ、全員が勝者となります。計算量は、ソートにO(n log n)、合計の計算にO(n)と非常に効率的です。

実装例

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

#include <bits/stdc++.h>
using namespace std;
bool solve(vector<int> A, int s){
    int k = 0;
    int n = A.size();
    sort(A.begin(), A.end());
    for (int i = 0; i < n - 1; i++)
        k += A[i];
    if (k > s)
        return false;
    else
        return true;
}
int main(){
    vector<int> A = { 3, 1, 3 };
    int s = 4;
    cout << solve(A, s) << endl;
}

入力

{ 3, 1, 3 }, 4

出力

1