C++で解く：体重計を爆発させずに金貨を載せる順序を見つけるアルゴリズム

n個の相異なる要素からなる配列Aと、整数xが与えられます。ここにn枚の金貨があり、i番目の金貨の重さはA[i]です。これらの金貨を体重計に1枚ずつ順番に載せていきます。ただし、この体重計には奇妙な欠陥があり、載せた金貨の合計重量がちょうどxになると爆発してしまいます。

すべての金貨を爆発させることなく体重計に載せられるかどうかを判定し、可能であればその順序を求めてください。不可能な場合は「IMPOSSIBLE」を出力します。

例えば、入力が A = [1, 2, 3, 4, 8]、x = 6 の場合、出力は [8, 1, 2, 3, 4] となります(他の順序も有効です)。

解法のステップ

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

s := 0
n := Aのサイズ
i := 0 で初期化し、i < n の間、i を 1 ずつ増やしながら実行:
    s := s + A[i]
s が x と等しい場合:
    "IMPOSSIBLE" を返す
s := 0
i := 0 で初期化し、i < n の間、i を 1 ずつ増やしながら実行:
    s := s + A[i]
    s が x と等しい場合:
        A[i + 1], A[i] の順に出力
        i を 1 増やす
        以降の処理をスキップして次の反復へ
    A[i] を出力

アルゴリズムのポイント

この解法が正しく動作する理由は次のとおりです。

• 総和がxと等しい場合: すべての金貨を載せ終えた時点で、体重計上の合計重量は必ず配列の総和になります。そのため総和がxなら、どのような順序で載せても最後に爆発してしまいます。よって「IMPOSSIBLE」を出力します。
• 総和がxと異なる場合: 配列の先頭から順に金貨を載せていく貪欲法を使います。累積和がちょうどxになってしまったときは、現在の金貨と次の金貨の順序を入れ替えます。すべての要素が相異なるため(A[i] ≠ A[i+1])、入れ替え後の累積和がxと一致することはなく、安全に処理を続けられます。

配列を2回走査するだけでよいため、計算量はO(n)という非常に効率的な手法です。

実装例

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

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

void solve(vector<int> A, int x) {
    int s = 0;
    int n = A.size();
    for (int i = 0; i < n; i++) {
        s += A[i];
    }
    if (s == x) {
        cout << "IMPOSSIBLE";
        return;
    }
    s = 0;
    for (int i = 0; i < n; i++) {
        s += A[i];
        if (s == x) {
            cout << A[i + 1] << ", " << A[i] << ", ";
            i++;
            continue;
        }
        cout << A[i] << ", ";
    }
}
int main() {
    vector<int> A = { 1, 2, 3, 4, 8 };
    int x = 6;
    solve(A, x);
}

入力

{ 1, 2, 3, 4, 8 }, 6

出力

1, 2, 4, 3, 8,

この出力では、各時点での累積重量は 1 → 3 → 7 → 10 → 18 と変化し、途中でx=6に一致することがないため、体重計は爆発せずにすべての金貨を載せることができます。