ABC133-D Rain Flows into Dams

問題へのリンク

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("3");
            WillReturn.Add("2 2 4");
            //4 0 4
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("5");
            WillReturn.Add("3 8 7 5 5");
            //2 4 12 2 8
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("3");
            WillReturn.Add("1000000000 1000000000 0");
            //0 2000000000 0
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

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

        long[] AArr = InputList[1].Split(' ').Select(pX => long.Parse(pX)).ToArray();
        int UB = AArr.GetUpperBound(0);

        var AnswerList = new List<long>();

        // 最初のノードの値を求める
        long UhenSum = 0;
        for (int I = 0; I <= UB; I++) {
            if (I % 2 == 0) {
                UhenSum += AArr[I];
            }
            else {
                UhenSum -= AArr[I];
            }
        }
        AnswerList.Add(UhenSum / 2);

        for (int I = 1; I <= UB; I++) {
            AnswerList.Add(AArr[I - 1] - AnswerList[I - 1]);
        }

        // 全てのノードの値を2倍する
        for (int I = 0; I <= AnswerList.Count - 1; I++) {
            AnswerList[I] *= 2;
        }

        string[] WillOutStrArr = Array.ConvertAll(AnswerList.ToArray(), pX => pX.ToString());
        Console.WriteLine(string.Join(" ", WillOutStrArr));
    }
}

解説

各ノードの値が、接続した2辺に、半分ずつ分配されると2で割る必要があって複雑になるので
半分にならずに分配されると考えて、最後に2倍することにします。

3 8 7 5 5
の入力について考えると
一番上のノードの値をXとすると
次のノードの値から、
3-X
8-3+X
7-8+3-X
5-7+8-3+X
5-5+7-8+3-X

で
X = 5-5+7-8+3-X
を移項すると
2X = 5-5+7-8+3
になってXの値が分かって
芋づる的に、他のノードの値も分かります。