C++で解く！ブロックタワーの高さの差（醜さ）を最小化するプログラム

n個の要素を持つ配列Aがあるとします。一列にn個のブロックタワーが並んでおり、i番目のタワーの高さはA[i]です。1日ごとに、次の操作を1回だけ実行できます。

「2つの異なるインデックスiとj（i ≠ j）を選び、タワーiからタワーjへブロックを1つ移動する」——この操作により、A[i]は1減少し、A[j]は1増加します。

建物の「醜さ」とは、max(A) − min(A)、すなわち最も高いタワーと最も低いタワーの高さの差として定義されます。この記事では、達成可能な最小の醜さを求める方法を解説します。

問題の例

例として、入力がA = [1, 2, 3, 1, 5]の場合を考えてみましょう。このときの出力は1になります。

• i = 2、j = 0として操作を3回行うと、配列は[2, 2, 2, 1, 5]になります。
• 次にi = 4、j = 3とすると、配列は[2, 2, 2, 2, 4]になります。
• さらにi = 4、j = 2とすると、配列は[2, 2, 3, 2, 3]となり、この時点での醜さは3 − 2 = 1です。

解法のポイント

この問題の鍵となるのは、「すべてのタワーの高さの合計値」に注目することです。

• 合計がnで割り切れる場合：全タワーを同じ高さ（合計 ÷ n）に揃えることができるため、醜さの最小値は0になります。
• 合計がnで割り切れない場合：タワーの高さは整数であるため、どうしても最低1の差が残ってしまいます。一方、ブロックは自由に移動できるため、差を1まで縮めることは必ず可能です。したがって、醜さの最小値は1になります。

手順

以上を踏まえ、以下の手順に従って問題を解きます。

sum := 0
x := 0
n := size of A
for initialize i := 0, when i < n, update (increase i by 1), do:
    sum := sum + A[i]
if sum mod n is same as 0, then:
    return 0
return 1

C++での実装例

理解を深めるために、実際のC++コードを見てみましょう。

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

int solve(vector<int> A) {
    int sum = 0, x = 0;
    int n = A.size();
    for (int i = 0; i < n; i++)
        sum += A[i];
    if (sum % n == 0)
        return 0;
    return 1;
}
int main() {
    vector<int> A = { 1, 2, 3, 1, 5 };
    cout << solve(A) << endl;
}

入力

{ 1, 2, 3, 1, 5 }

出力

1

このように、合計値を要素数nで割った余りが0かどうかを確認するだけで、O(n)の計算量で答えを求められる非常にシンプルなアルゴリズムとなっています。