ARC135-B Sum of Three Terms

問題へのリンク

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("5");
            WillReturn.Add("6 9 6 6 5");
            //Yes
            //0 4 2 3 1 2 2
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("5");
            WillReturn.Add("0 1 2 1 0");
            //No
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("1");
            WillReturn.Add("10");
            //Yes
            //0 0 10
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();
        long[] SArr = InputList[1].Split(' ').Select(pX => long.Parse(pX)).ToArray();

        long[] AnswerArr = new long[SArr.Length + 2];

        // mod 3 で 0の場所の値を決める
        var ValSet = new HashSet<long>();
        AnswerArr[0] = 0;
        ValSet.Add(0);
        for (int I = 3; I <= AnswerArr.GetUpperBound(0); I += 3) {
            AnswerArr[I] = AnswerArr[I - 3] + SArr[I - 2] - SArr[I - 3];
            ValSet.Add(AnswerArr[I]);
        }
        if (ValSet.Min() < 0) {
            long Geta = Math.Abs(ValSet.Min());
            for (int I = 0; I <= AnswerArr.GetUpperBound(0); I += 3) {
                AnswerArr[I] += Geta;
            }
        }

        // mod 3 で 1の場所の値を決める
        ValSet.Clear();
        AnswerArr[1] = 0;
        ValSet.Add(0);
        for (int I = 4; I <= AnswerArr.GetUpperBound(0); I += 3) {
            AnswerArr[I] = AnswerArr[I - 3] + SArr[I - 2] - SArr[I - 3];
            ValSet.Add(AnswerArr[I]);
        }
        if (ValSet.Min() < 0) {
            long Geta = Math.Abs(ValSet.Min());
            for (int I = 1; I <= AnswerArr.GetUpperBound(0); I += 3) {
                AnswerArr[I] += Geta;
            }
        }

        // mod 3 で 2の場所の値を決める
        for (int I = 2; I <= AnswerArr.GetUpperBound(0); I += 3) {
            AnswerArr[I] = SArr[I - 2] - AnswerArr[I - 2] - AnswerArr[I - 1];
        }

        // 十分性のチェック
        bool IsOK = true;
        if (Array.Exists(AnswerArr, pX => pX < 0)) {
            IsOK = false;
        }
        for (int I = 2; I <= AnswerArr.GetUpperBound(0); I++) {
            long Sum = AnswerArr[I - 2] + AnswerArr[I - 1] + AnswerArr[I];
            if (Sum != SArr[I - 2]) {
                IsOK = false;
            }
        }

        if (IsOK) {
            Console.WriteLine("Yes");

            // セパレータとLong型の列挙を引数として、結合したstringを返す
            Func<string, IEnumerable<long>, string> LongEnumJoin = (pSeparater, pEnum) =>
            {
                string[] StrArr = Array.ConvertAll(pEnum.ToArray(), pX => pX.ToString());
                return string.Join(pSeparater, StrArr);
            };

            Console.WriteLine(LongEnumJoin(" ", AnswerArr));
        }
        else {
            Console.WriteLine("No");
        }
    }
}

解説

6 9 6 6 5
で考えます。

    6 9 6 6 5
A B C D E F G
という図を書くと

A+B+C = 6
B+C+D = 9
C+D+E = 6
D+E+F = 6
E+F+G = 5
が成り立つと分かります。

Aを0に仮決めすると
添え字の3つ飛ばしでDとGを決定できます。

Bを0に仮決めすると
添え字の3つ飛ばしでEを決定できます。

負数がNGなので
Aを0に仮決めした際に、
DかGに負数が発生したら、
A,D,Gに負数の絶対値を足して、
負数を防ぎます。

Bを0に仮決めした際に、
Eが負数になったら、
B,Eに負数の絶対値を足して、
負数を防ぎます。

AとBが決定したら、残りの数も決まるので
全ての数を仮決めします。

最後に十分性を確認すれば、解が求まります。