競技プログラミングの鉄則    次の問題へ    前の問題へ

B45 Blackboard 2


問題へのリンク


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 -4 1");
            //Yes
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();
        long[] wkArr = InputList[0].Split(' ').Select(pX => long.Parse(pX)).ToArray();
        long A = wkArr[0];
        long B = wkArr[1];
        long C = wkArr[2];

        if (A + B + C == 0) {
            Console.WriteLine("Yes");
        }
        else {
            Console.WriteLine("No");
        }
    }
}


解説

不変量に着目すると
A+B+Cは不変だと分かる。

ゴールの状態は、A=B=C=0であり
A=B=C=0 ⇒ A+B+C=0
よって、
必要条件 A+B+C = 0 が導出できる

十分性
A+B+C=0 ⇒ ゴールに到達可能
を確認します。

まず、場合分けします
場合1 A,B,Cが3つとも0の場合
これは、ゴールの条件を満たします

場合2 A,B,Cに0以外が存在する場合
A+B+C=0なので
正の数の総合計 = 負の数の総合計
であり、2つの数を選んで++と--を何度も実行すれば
ゴールに到達できます。