ABC-043-C いっしょ

■■■問題■■■

N個の整数 a1,a2 ・・・ aN が与えられます。
えび君はこれらを書き換えて全て同じ整数にしようとしています。
各ai(1 <= i <= N)は高々1回しか書き換えられません(書き換えなくても良い)。

整数xを整数yに書き換えるとき、コストが(x-y)の2乗かかります。
仮にai=aj (i≠j)だとしても、
ひとつ分のコストで同時に書き換えることは出来ません(入出力例2を参照)。

えび君が目的を達成するのに必要なコストの総和の最小値を求めてください。

■■■入力■■■

N
a1 a2 ・・・ aN

●1 <= N <= 100
●-100 <= ai <= 100

■■■出力■■■

えび君が全てを同じ整数に書き換えるのに必要なコストの総和の最小値を出力せよ。

C#のソース

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static string InputPattern = "InputX";

    static List<string> GetInputList()
    {
        var WillReturn = new List<string>();

        if (InputPattern == "Input1") {
            WillReturn.Add("2");
            WillReturn.Add("4 8");
            //8
            //全てを6に書き換えると、
            //コストの総和は(4-6)の2乗 + (8-6)の2乗 = 8となり、
            //これが最小です。
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("3");
            WillReturn.Add("1 1 3");
            //3
            //全てを2に書き換えると
            //(1-2)の2乗+(1-2)の2乗+(3-2)の2乗=3となります。
            //各aiごとに書き換えるので、
            //二つの1を一度にコスト(1-2)の2乗で
            //書き換えられるわけではないことに注意してください。
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("3");
            WillReturn.Add("4 2 5");
            //5
            //4は書き換えずに、2と5を共に4に書き換えることで
            //(2-4)の2乗 + (5-4)の2乗 = 5が達成できて、
            //これが最小です。
        }
        else if (InputPattern == "Input4") {
            WillReturn.Add("4");
            WillReturn.Add("-100 -100 -100 -100");
            //0
            //何も書き換えなくともえび君は目的を達成しています。
            //よってこの場合コストは0です。
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();
        int[] AArr = InputList[1].Split(' ').Select(X => int.Parse(X)).ToArray();

        int ASum = AArr.Sum();

        var AvgList = new List<int>();
        if (ASum % AArr.Length == 0)
            AvgList.Add(ASum / AArr.Length);
        else {
            if (ASum > 0) {
                AvgList.Add(ASum / AArr.Length);
                AvgList.Add(ASum / AArr.Length + 1);
            }
            else {
                AvgList.Add(ASum / AArr.Length);
                AvgList.Add(ASum / AArr.Length - 1);
            }
        }

        int Answer = int.MaxValue;
        foreach (int EachAvg in AvgList) {
            int DiffJijyouSum = 0;
            foreach (int EachInt in AArr) {
                DiffJijyouSum += (EachAvg - EachInt) * (EachAvg - EachInt);
            }
            if (DiffJijyouSum < Answer)
                Answer = DiffJijyouSum;
        }
        Console.WriteLine(Answer);
    }
}

解説

平均値を小数切捨てと切り上げの2通りで、
差の2乗の和が小さいほうを解としてます。

平均値が小数を含まなかった場合は、分散が解になります。

メモ 2016-08-13 統計や分散について勉強してから、再検証すること