ARC049-B 高橋ノルム君

問題へのリンク

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("2");
            WillReturn.Add("0 0 1");
            WillReturn.Add("10 10 1");
            //5.000000000000000
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("2");
            WillReturn.Add("0 0 1");
            WillReturn.Add("10 10 2");
            //6.666666666666667
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("10");
            WillReturn.Add("-27 -67 10");
            WillReturn.Add("59 13 10");
            WillReturn.Add("14 -15 9");
            WillReturn.Add("-29 -84 7");
            WillReturn.Add("-75 -2 2");
            WillReturn.Add("-12 -74 5");
            WillReturn.Add("77 31 9");
            WillReturn.Add("40 64 8");
            WillReturn.Add("-81 32 1");
            WillReturn.Add("81 26 5");
            //582.222222222222222
        }
        else if (InputPattern == "Input4") {
            WillReturn.Add("8");
            WillReturn.Add("-81739 73917 446");
            WillReturn.Add("42230 30484 911");
            WillReturn.Add("79354 -50126 200");
            WillReturn.Add("33440 -47087 651");
            WillReturn.Add("-73 84114 905");
            WillReturn.Add("79222 -53608 713");
            WillReturn.Add("65194 -46284 685");
            WillReturn.Add("81145 40933 47");
            //54924095.383189122374461
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    struct XYCInfoDef
    {
        internal double X;
        internal double Y;
        internal double C;
    }
    static List<XYCInfoDef> mXYCInfoList = new List<XYCInfoDef>();

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

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

        foreach (string EachStr in InputList.Skip(1)) {
            SplitAct(EachStr);
            XYCInfoDef WillAdd;
            WillAdd.X = wkArr[0];
            WillAdd.Y = wkArr[1];
            WillAdd.C = wkArr[2];
            mXYCInfoList.Add(WillAdd);
        }

        double XCostMin = DeriveXCostMin();
        double YCostMin = DeriveYCostMin();
        var AnswerKouhoList = new List<double>();
        AnswerKouhoList.Add(XCostMin);
        AnswerKouhoList.Add(YCostMin);
        Console.WriteLine(AnswerKouhoList.Max());
    }

    // 三分探索でX方向の移動の極小値を求める
    static double DeriveXCostMin()
    {
        double L = mXYCInfoList.Min(pX => pX.X);
        double R = mXYCInfoList.Max(pX => pX.X);

        var PairHashSet = new HashSet<string>();
        while (L + double.Epsilon < R) {
            double C1 = (L * 2 + R) / 3;
            double C2 = (L + R * 2) / 3;

            double C1Val = DeriveXCost(C1);
            double C2Val = DeriveXCost(C2);

            if (C1Val < C2Val) {
                R = C2;
            }
            else {
                L = C1;
            }

            string Hash = string.Format("{0},{1}", L, R);
            if (PairHashSet.Add(Hash) == false) {
                break;
            }
        }
        var MinKouhoList = new List<double>();
        MinKouhoList.Add(DeriveXCost(L));
        MinKouhoList.Add(DeriveXCost(R));
        return MinKouhoList.Min();
    }

    // X座標を引数として、必要時間の最大値を返す
    static double DeriveXCost(double pBaseX)
    {
        double WillReturn = double.MinValue;
        foreach (XYCInfoDef EachXYCInfo in mXYCInfoList) {
            double CurrCost = EachXYCInfo.C * Math.Abs(pBaseX - EachXYCInfo.X);
            WillReturn = Math.Max(WillReturn, CurrCost);
        }
        return WillReturn;
    }

    // 三分探索でY方向の移動の極小値を求める
    static double DeriveYCostMin()
    {
        double L = mXYCInfoList.Min(pX => pX.Y);
        double R = mXYCInfoList.Max(pX => pX.Y);

        var PairHashSet = new HashSet<string>();
        while (L + double.Epsilon < R) {
            double C1 = (L * 2 + R) / 3;
            double C2 = (L + R * 2) / 3;

            double C1Val = DeriveYCost(C1);
            double C2Val = DeriveYCost(C2);

            if (C1Val < C2Val) {
                R = C2;
            }
            else {
                L = C1;
            }

            string Hash = string.Format("{0},{1}", L, R);
            if (PairHashSet.Add(Hash) == false) {
                break;
            }
        }
        var MinKouhoList = new List<double>();
        MinKouhoList.Add(DeriveYCost(L));
        MinKouhoList.Add(DeriveYCost(R));
        return MinKouhoList.Min();
    }

    // Y座標を引数として、必要時間の最大値を返す
    static double DeriveYCost(double pBaseY)
    {
        double WillReturn = double.MinValue;
        foreach (XYCInfoDef EachXYCInfo in mXYCInfoList) {
            double CurrCost = EachXYCInfo.C * Math.Abs(pBaseY - EachXYCInfo.Y);
            WillReturn = Math.Max(WillReturn, CurrCost);
        }
        return WillReturn;
    }
}

解説

C * max(X座標の差 , Y座標の差)
の最大値を最小化にしたいので

X座標の差の最大値を最小化しつつ
Y座標の差の最大値を最小化したものは
解の一つとなります。

数式に着目すれば、
X座標の最小値からX座標の最大値の区間で極小値を持つと分かるので
三分探索で解けます。