C++で石積みの数を検証する方法：翌日の状態が有効かどうかを判定する

問題の概要

同じサイズを持つ2つの配列 X と Y があるとします。1日目の時点で、i番目の場所には X[i] 個の石が積まれた山があります。そして2日目には、同じ場所に Y[i] 個の石が積まれています。

1日目に多くのメンバーが訪れ、彼らは次のいずれかの行動を取ったと考えられます。

• 何もしない
• いくつかの山に石を追加する
• ある山から別の山へ石を移し替える

このとき、Y が X から導ける正当な状態かどうかを判定する必要があります。

たとえば、入力が X = [1, 2, 3, 4, 5]、Y = [2, 1, 4, 3, 5] の場合、出力は True になります。なぜなら、2番目の山から1番目の山へ1個、4番目の山から3番目の山へ1個の石を移動させるだけで Y の状態を作れるからです。

解法のポイント

メンバーができるのは「石の追加」または「山同士の移動」だけなので、石の総数は減ることがありません。つまり、Y の合計が X の合計以上であれば、その状態は達成可能だと判断できます。

アルゴリズムの手順

この問題は以下の手順で解くことができます。

• 配列 A(X)の要素の合計 s を求める
• 配列 B(Y)の要素の合計 d を求める
• d > s であれば false を返し、そうでなければ true を返す

n := size of A
for initialize i := 0, when i < n, update (increase i by 1), do:
    s := s + A[i]
for initialize i := 0, when i < n, update (increase i by 1), do:
    d := d + B[i]
return (if d > s, then false, otherwise true)

C++による実装例

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

#include <bits/stdc++.h>
using namespace std;
bool solve(vector<int> A, vector<int> B){
    int n = A.size(), d = 0, s = 0;
    for (int i = 0; i < n; i++)
        s += A[i];
    for (int i = 0; i < n; i++)
        d += B[i];
    return d > s ? false : true;
}
int main(){
    vector<int> X = { 1, 2, 3, 4, 5 };
    vector<int> Y = { 2, 1, 4, 3, 5 };
    cout << solve(X, Y) << endl;
}

入力

{ 1, 2, 3, 4, 5 }, { 2, 1, 4, 3, 5 }

出力

1

まとめ

このアルゴリズムの計算量は O(n) で、配列を一度ずつ走査するだけで判定が完了します。石の総数が増えることはあっても減ることはないという性質に着目することで、シンプルかつ効率的に問題を解くことができます。