C++で2つのコンサートの演奏時間差の最小値を求める方法

3つの整数 a、b、c が与えられます。ある歌手は、1分の曲を a 曲、2分の曲を b 曲、3分の曲を c 曲持っています。歌手はすべての曲を2つのコンサートに振り分けたいと考えていますが、各曲は必ずどちらか一方のコンサートにのみ含まれる必要があります。歌手の目標は、2つのコンサートの演奏時間(それぞれのコンサートに含まれる全曲の時間の合計)の絶対差をできるだけ小さくすることです。ここで、コンサート間の演奏時間差として考えられる最小値を求めます。

具体例

入力が a = 2、b = 1、c = 3 の場合を考えてみましょう。このときの出力は 1 になります。

1つ目のコンサートに「1分の曲2本」「2分の曲1本」「3分の曲1本」を入れ、2つ目のコンサートに「3分の曲2本」を入れるとします。すると、1つ目のコンサートの演奏時間は 1 + 1 + 2 + 3 = 7 分、2つ目のコンサートは 3 + 3 = 6 分となり、差は |7 − 6| = 1 です。これ以上差を小さくすることはできません。

解法のポイント

この問題は、全曲の合計時間の「偶奇」に注目すると O(1) で解くことができます。

• 全曲の合計時間は T = a × 1 + b × 2 + c × 3 = a + 2b + 3c と表せる
• 2b は常に偶数なので、T の偶奇は (a + c) の偶奇と一致する
• T が偶数の場合：曲をうまく振り分ければ両方のコンサートの時間を等しくできるため、最小差は 0
• T が奇数の場合：どのように分割しても差は最低 1 になり、実際に差 1 の分割が可能なので、最小差は 1

したがって、答えは「(a + c) を 2 で割った余り」、つまり a + c が偶数なら 0、奇数なら 1 となります。2分の曲の本数 b は偶奇に影響しないため、答えの計算には不要です。

C++での実装例

以下の実装を見ると、仕組みがより理解しやすくなります。

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

int solve(int a, int b, int c) {
    // 2分の曲(b)は合計の偶奇に影響しないため、
    // a と c の偶奇だけで判定できる
    return (a + c) % 2;
}

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

入力

2, 1, 3

出力

1

まとめ

一見するとナップサック問題のような難しい組み合わせ最適化に思えますが、曲の長さが1分・2分・3分と小さいことを利用すると、合計時間の偶奇だけを確認すればよいことが分かります。計算量は O(1) という非常にシンプルで効率的な解法です。