ABC196-E Filters

問題へのリンク

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("-10 2");
            WillReturn.Add("10 1");
            WillReturn.Add("10 3");
            WillReturn.Add("5");
            WillReturn.Add("-15 -10 -5 0 5");
            //0
            //0
            //5
            //10
            //10
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    struct ATInfoDef
    {
        internal long A;
        internal long T;
    }
    static List<ATInfoDef> mATInfoList = new List<ATInfoDef>();

    static long[] mXArr;

    static void Main()
    {
        List<string> InputList = GetInputList();
        long N = int.Parse(InputList[0]);

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

        foreach (string EachStr in InputList.Skip(1).Take((int)N)) {
            SplitAct(EachStr);
            ATInfoDef WillAdd;
            WillAdd.A = wkArr[0];
            WillAdd.T = wkArr[1];
            mATInfoList.Add(WillAdd);
        }
        mXArr = InputList.Last().Split(' ').Select(pX => long.Parse(pX)).ToArray();

        bool HasT2 = mATInfoList.Exists(pX => pX.T == 2);
        bool HasT3 = mATInfoList.Exists(pX => pX.T == 3);

        long X2 = long.MinValue;
        long Y2 = long.MinValue;
        if (HasT2) {
            X2 = DeriveMinY_MaxX();
            Y2 = DeriveResult(X2);
        }

        long X3 = long.MaxValue;
        long Y3 = long.MaxValue;
        if (HasT3) {
            X3 = DeriveMaxY_MinX();
            Y3 = DeriveResult(X3);
        }

        long ASum = mATInfoList.Sum(pX => pX.A);

        var sb = new System.Text.StringBuilder();
        foreach (long EachX in mXArr) {
            if (EachX <= X2) {
                sb.AppendLine(Y2.ToString());
                continue;
            }
            if (X3 <= EachX) {
                sb.AppendLine(Y3.ToString());
                continue;
            }

            if (HasT2 == false && HasT3 == false) {
                sb.AppendLine((EachX + ASum).ToString());
                continue;
            }
            if (HasT2) {
                long Diff = X2 - EachX;
                sb.AppendLine((Y2 - Diff).ToString());
                continue;
            }
            if (HasT3) {
                long Diff = EachX - X3;
                sb.AppendLine((Y3 + Diff).ToString());
                continue;
            }
        }
        Console.Write(sb.ToString());
    }

    // 関数を順番に適用した結果を返す
    static long DeriveResult(long pX)
    {
        long WillReturn = pX;
        foreach (ATInfoDef EachATInfo in mATInfoList) {
            long T = EachATInfo.T;
            long A = EachATInfo.A;
            if (T == 1) {
                WillReturn += A;
            }
            if (T == 2) {
                WillReturn = Math.Max(WillReturn, A);
            }
            if (T == 3) {
                WillReturn = Math.Min(WillReturn, A);
            }
        }
        return WillReturn;
    }

    // Yが最小値になるXの最大値を求める
    static long DeriveMinY_MaxX()
    {
        long AbsASum = mATInfoList.Sum(pX => Math.Abs(pX.A));
        long MinY = DeriveResult(-AbsASum * 2);

        long L = -AbsASum * 2;
        long R = AbsASum * 2;

        while (L + 1 < R) {
            long Mid = (L + R) / 2;

            if (DeriveResult(Mid) == MinY) {
                L = Mid;
            }
            else {
                R = Mid;
            }
        }
        return L;
    }

    // Yが最大値になるXの最小値を求める
    static long DeriveMaxY_MinX()
    {
        long AbsASum = mATInfoList.Sum(pX => Math.Abs(pX.A));
        long MaxY = DeriveResult(AbsASum * 2);

        long L = -AbsASum * 2;
        long R = AbsASum * 2;

        while (L + 1 < R) {
            long Mid = (L + R) / 2;

            if (DeriveResult(Mid) == MaxY) {
                R = Mid;
            }
            else {
                L = Mid;
            }
        }
        return R;
    }
}

解説

T=2の関数と、T=3の関数があるかで場合分けしつつ

合成関数の結果が
最小値を取る区間と最大値を取る区間
を二分法で求めてます。