【C++】4つのキャンディーの袋を2人の友人に均等に分配できるか判定するプログラム

問題概要

4つの要素を持つ配列 A があるとします。これは4つのキャンディーの袋を表しており、i 番目の袋には A[i] 個のキャンディーが入っています。これらの袋をすべて2人の友人のどちらかに配りたいと考えています。各袋をどちらか一方の友人に割り振るとき、2人が受け取るキャンディーの合計数を同じにできるかどうかを判定するのが課題です。

例として、入力が A = [1, 7, 11, 5] の場合を考えてみましょう。この場合、出力は True になります。1番目と3番目の袋（1＋11＝12個）を1人目の友人に、2番目と4番目の袋（7＋5＝12個）を2人目の友人に渡すことで、両者とも合計12個のキャンディーを受け取れるからです。

解決手順

この問題は、4つの袋の分け方のパターンをすべて確認することで解決できます。具体的には次の手順に従います。

a := A[0]
b := A[1]
c := A[2]
d := A[3]
if (a + b) == (c + d) または (a + c) == (b + d) または (a + d) == (b + c) または
   (a + b + c) == d または (a + b + d) == c または (a + c + d) == b または
   (b + c + d) == a の場合:
    return true
それ以外の場合:
    return false

4つの袋を2人で分ける場合、「2袋ずつ」または「1袋と3袋」のいずれかのパターンしか存在しません。そのため、考えられるすべての組み合わせについて合計が一致するかをチェックすればよいことになります。一見条件式が多く感じられますが、片方の友人が受け取る袋の組み合わせを列挙しているだけなので、計算量はごくわずかで済みます。

実装例

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

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

bool solve(vector<int> A) {
    int a = A[0];
    int b = A[1];
    int c = A[2];
    int d = A[3];
    if (a + b == c + d || a + c == b + d || a + d == b + c || a + b + c == d || a + b + d == c || a + c + d == b || b + c + d == a)
        return true;
    else
        return false;
}
int main() {
    vector<int> A = { 1, 7, 11, 5 };
    cout << solve(A) << endl;
}

入力

1, 7, 11, 5

出力

1

出力が「1」と表示されていますが、これは bool 型の true が整数値 1 として出力されたことを意味します。つまり、この入力に対しては2人の友人にキャンディーを均等に分配できると判定されたことになります。