C++で最小の算術平均偏差を求めるアルゴリズムと実装例

問題の概要

3つの要素を持つ配列Aを考えます。A[0] + A[2] = 2 × A[1] が成り立つとき、A[1]はA[0]とA[2]の相加平均（算術平均）であるといえます。3つの数の算術平均偏差 d(A[0], A[1], A[2]) は、次の式で定義されます。

d(A[0], A[1], A[2]) = |A[0] + A[2] − 2 × A[1]|

ここで、次の操作を何度でも実行できるものとします。インデックス {0, 1, 2} から異なる2つのインデックス i と j を選び、A[i] を1増やして A[j] を1減らします。このとき、達成できる算術平均偏差の最小値を求めてください。

入力例と出力例

入力が A = [2, 2, 6] の場合、出力は 1 になります。A[0] を1減らして A[1] を1増やすと、配列は [1, 3, 6] となり、平均偏差は |1 + 6 − 2 × 3| = 1 となるためです。

解法のアプローチ

この問題は、次の手順でO(1)で解くことができます。

• a := A[0]、b := A[1]、c := A[2] とします。
• 1 と ((a + c − 2 × b) mod 3 + 3) mod 3 のうち小さい方を返します。

なぜ「mod 3」で求まるのか

ポイントは、各操作によって値 V = a + c − 2b が必ず 0 または ±3 ずつ変化することです。例えば、i = 0 を増やして j = 1 を減らすと V は +3 変化し、i = 0 を増やして j = 2 を減らすと変化量は 0 になります。つまり、V を3で割った余りはどのような操作を行っても不変です。

したがって、余りが0の場合は操作を繰り返すことで偏差をちょうど0にでき、余りが1または2の場合は絶対値を1未満にできません。よって答えは min(1, V mod 3) となります。C++では負の数に対する % 演算の結果が負になる可能性があるため、((V % 3) + 3) % 3 という形で正規化しています。

C++での実装例

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

int solve(vector<int> A)
{
    int a = A[0];
    int b = A[1];
    int c = A[2];
    return min(1, ((a + c - 2 * b) % 3 + 3) % 3);
}

int main()
{
    vector<int> A = { 2, 2, 6 };
    cout << solve(A) << endl;
}

入力

{ 2, 2, 6 }

出力

1