yukicoder 2927 Reverse Polish Equation

問題へのリンク

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 5");
            WillReturn.Add("X 2 +");
            //3
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("7 9");
            WillReturn.Add("X X 3 max + 11 min");
            //-1
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("11 10");
            WillReturn.Add("X X X X X + + + + 10 max");
            //0
        }
        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 Y = wkArr[1];

        string[] ExpArr = InputList[1].Split(' ');

        decimal Result0 = ExecCalc(0, ExpArr);
        if (Result0 == Y) {
            Console.WriteLine(0);
            return;
        }
        if (Result0 > Y) {
            Console.WriteLine(-1);
            return;
        }

        if (ExecCalc(Y, ExpArr) < Y) {
            Console.WriteLine(-1);
            return;
        }

        long L = 0;
        long R = Y;

        while (L + 1 < R) {
            long Mid = (L + R) / 2;
            if (ExecCalc(Mid, ExpArr) >= Y) {
                R = Mid;
            }
            else {
                L = Mid;
            }
        }

        decimal Result = ExecCalc(R, ExpArr);
        if (Result == Y) {
            Console.WriteLine(R);
        }
        else {
            Console.WriteLine(-1);
        }
    }

    // Xの値と、文字列を引数として、計算結果を返す
    static decimal ExecCalc(long pX, string[] pExpArr)
    {
        var Stk = new Stack<decimal>();
        foreach (string EachExp in pExpArr) {
            if (EachExp == "+" || EachExp == "min" || EachExp == "max") {
                decimal Popped1 = Stk.Pop();
                decimal Popped2 = Stk.Pop();
                decimal CalcResult = 0;
                if (EachExp == "+") CalcResult = Popped1 + Popped2;
                if (EachExp == "min") CalcResult = Math.Min(Popped1, Popped2);
                if (EachExp == "max") CalcResult = Math.Max(Popped1, Popped2);
                Stk.Push(CalcResult);
            }
            else {
                if (EachExp == "X") {
                    Stk.Push(pX);
                }
                else {
                    Stk.Push(decimal.Parse(EachExp));
                }
            }
        }
        return Stk.Peek();
    }
}

解説

オペランドが、+とminとmaxしかないので
計算結果は、Xに対して、広義単調増加です。

なので、二分探索で解けます。