ABC112-C Pyramid

問題へのリンク

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 3 5");
            WillReturn.Add("2 1 5");
            WillReturn.Add("1 2 5");
            WillReturn.Add("3 2 5");
            //2 2 6
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("2");
            WillReturn.Add("0 0 100");
            WillReturn.Add("1 1 98");
            //0 0 100
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("3");
            WillReturn.Add("99 1 191");
            WillReturn.Add("100 1 192");
            WillReturn.Add("99 0 192");
            //100 0 193
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    struct XYHInfoDef
    {
        internal int X;
        internal int Y;
        internal int H;
    }
    static List<XYHInfoDef> mXYHInfoList = new List<XYHInfoDef>();

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

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

        foreach (string EachStr in InputList.Skip(1)) {
            SplitAct(EachStr);
            XYHInfoDef WillAdd;
            WillAdd.X = wkArr[0];
            WillAdd.Y = wkArr[1];
            WillAdd.H = wkArr[2];
            mXYHInfoList.Add(WillAdd);
        }
        // 高さでソートしておく
        mXYHInfoList = mXYHInfoList.OrderByDescending(pX => pX.H).ToList();

        // 中心のX座標とY座標を全探索
        for (int CenterX = 0; CenterX <= 100; CenterX++) {
            for (int CenterY = 0; CenterY <= 100; CenterY++) {
                int CenterHeight;
                if (IsOK(CenterX, CenterY, out CenterHeight)) {
                    Console.WriteLine("{0} {1} {2}", CenterX, CenterY, CenterHeight);
                    return;
                }
            }
        }
    }

    static bool IsOK(int pCenterX, int pCenterY, out int pCenterHeight)
    {
        pCenterHeight = 0;
        bool DerivedCenterHeight = false;

        foreach (XYHInfoDef EachXYHInfo in mXYHInfoList) {
            int XDiff = Math.Abs(EachXYHInfo.X - pCenterX);
            int YDiff = Math.Abs(EachXYHInfo.Y - pCenterY);

            if (DerivedCenterHeight == false) {
                pCenterHeight = EachXYHInfo.H + XDiff + YDiff;
                DerivedCenterHeight = true;
            }
            else {
                int CurrHegiht = Math.Max(pCenterHeight - XDiff - YDiff, 0);
                // 高さが違っていたらNG
                if (CurrHegiht != EachXYHInfo.H) {
                    return false;
                }
            }
        }
        return true;
    }
}

解説

中心座標の候補を全探索してます。

調査結果で高さが全て0だと、
中心の高さを決定できないので、
調査結果に、高さ1以上のものは必ず存在します。

なので、調査結果を高さの降順にソートし、
最初の1件でピラミッドの中心の高さを確定し、
調査結果の2件目以降では、高さに矛盾がないかをチェックしてます。