AtCoderのARC    次のARCの問題へ    前のARCの問題へ

ARC158-A +3 +5 +7


問題へのリンク


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("4");
            WillReturn.Add("2 8 8");
            WillReturn.Add("1 1 1");
            WillReturn.Add("5 5 10");
            WillReturn.Add("10 100 1000");
            //2
            //0
            //-1
            //315
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();

        long[] wkArr = { };
        Action<string> SplitAct = pStr =>
            wkArr = pStr.Split(' ').Select(pX => long.Parse(pX)).ToArray();

        foreach (string EachStr in InputList.Skip(1)) {
            SplitAct(EachStr);
            long p1 = wkArr[0];
            long p2 = wkArr[1];
            long p3 = wkArr[2];
            long Result = Solve(p1, p2, p3);
            Console.WriteLine(Result);
        }
    }

    static long Solve(long p1, long p2, long p3)
    {
        var ValList = new List<long>();
        ValList.Add(p1);
        ValList.Add(p2);
        ValList.Add(p3);

        // 必要条件1 偶奇が一致してること
        var Mod2Set = new HashSet<long>();
        ValList.ForEach(pX => Mod2Set.Add(pX % 2));
        if (Mod2Set.Count > 1) {
            return -1;
        }

        // 必要条件2 平均が整数であること
        long SumVal = ValList.Sum();
        if (SumVal % 3 > 0) {
            return -1;
        }

        long AvgVal = SumVal / 3;

        long PlusDiff = 0;
        long MinusDiff = 0;

        foreach (long EachVal in ValList) {
            if (EachVal > AvgVal) {
                PlusDiff += EachVal - AvgVal;
            }
            else {
                MinusDiff += AvgVal - EachVal;
            }
        }

        // 必要条件3 平均より多い分と、平均より小さい分が、一致すること
        if (PlusDiff != MinusDiff) {
            return -1;
        }

        // 必要条件4 平均より多い分と、平均より小さい分が、2の倍数であること
        if (PlusDiff % 2 > 0) return -1;
        if (MinusDiff % 2 > 0) return -1;

        // 解を返す
        return PlusDiff / 2;
    }
}


解説

3つの値を等しくできるかが問題なので
+3 +5 +7 は
+0 +2 +4 と同じ事です。

ここで必要条件1
3つの数の偶奇が一致してることが導けます。

+0 +2 +4 を変形し、
-2 +0 +2 にします。

すると、3つの数の合計は固定だと考えることができます。
3つの数の合計は不変で、
3つの数が等しくなるので
必要条件2 平均が整数であることが導けます。

必要条件3 平均より多い分と、平均より小さい分が、一致すること
必要条件4 平均より多い分と、平均より小さい分が、2の倍数であること
も考察で導くことができます。