C++で解くスーパー洗濯機問題 ― 最小移動回数を求めるアルゴリズム

一列に並んだ n 台のスーパー洗濯機があるとします。初期状態では、各洗濯機には何着かの服が入っているか、あるいは空になっています。1 回の移動ごとに、任意の m 台（1 ≤ m ≤ n）の洗濯機を選び、選んだ各洗濯機から 1 着ずつ、隣接する洗濯機へ同時に渡すことができます。

ここで、左から右へ各洗濯機に入っている服の枚数を表す整数配列が与えられます。すべての洗濯機の服の枚数を同じにするために必要な最小の移動回数を求めてください。均等にすることが不可能な場合は -1 を返します。

具体例

たとえば入力が [1, 0, 5] の場合、出力は 3 になります。手順は以下の通りです。

1. 右端の 5 から中央の 0 へ 1 着移す → 配列は [1, 1, 4]
2. 中央の 1 から左端へ、右端の 4 から中央へ同時に 1 着ずつ移す → 配列は [2, 1, 3]
3. 右端の 3 から中央へ 1 着移す → 配列は [2, 2, 2] となり完成

解き方のアプローチ

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

• sum := 配列 v の全要素の合計
• n := 配列 v のサイズ
• sum を n で割った余りが 0 でない場合 → 均等に分割できないので -1 を返す
• req := sum / n（各洗濯機が最終的に持つべき枚数）、ret := 0、extra := 0 とする
• i = 0 から n - 1 まで繰り返し：
  • x := v[i]
  • extra := extra + (x − req)（左側との累積的な過不足）
  • ret := { ret, x − req, |extra| } の最大値
• ret を返す

なぜこの方法で正しいのか

答えとなる下限は 2 つの要素のうち大きい方で決まります。

• 各洗濯機の余剰分（x − req）：1 回の移動で 1 台の洗濯機が出せる服は高々 1 着なので、余剰が k 着ある洗濯機は最低でも k 回の移動が必要です。
• 境界をまたぐ累積量（|extra|）：ある位置より左側全体の過不足分は、必ずその境界を横断して移動しなければなりません。1 回の移動で境界を越える服は 1 睪だけなので、これも移動回数の下限になります。

したがって、これらの最大値を全洗濯機について見れば、それがちょうど達成可能な最小移動回数となります。

C++ 実装例

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

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    int findMinMoves(vector<int>& v) {
        int sum = accumulate(v.begin(), v.end(), 0);
        int n = v.size();
        if(sum % n != 0) return -1;
        int req = sum / n;
        int ret = 0;
        int extra = 0;
        for(int i = 0; i < n; i++){
            int x = v[i];
            extra +=( x - req);
            ret = max({ret, x - req, abs(extra)});
        }
        return ret;
    }
};
main(){
    Solution ob;
    vector<int> v = {2,1,6};
    cout << (ob.findMinMoves(v));
}

入力

{2,1,6}

出力

3