ABC376-C Prepare Another Box

問題へのリンク

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("5 2 3 7");
            WillReturn.Add("6 2 8");
            //3
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("4");
            WillReturn.Add("3 7 2 5");
            WillReturn.Add("8 1 6");
            //-1
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("8");
            WillReturn.Add("2 28 17 39 57 56 37 32");
            WillReturn.Add("34 27 73 28 76 61 27");
            //37
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static int[] mAArr;
    static List<int> mBList;

    static void Main()
    {
        List<string> InputList = GetInputList();
        mAArr = InputList[1].Split(' ').Select(pX => int.Parse(pX)).ToArray();
        mBList = InputList[2].Split(' ').Select(pX => int.Parse(pX)).ToList();

        Array.Sort(mAArr);

        int L = 0;
        int R = mAArr.Max();

        // Rが達成不可な場合
        if (CanAchieve(R) == false) {
            Console.WriteLine(-1);
            return;
        }

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

            if (CanAchieve(Mid)) {
                R = Mid;
            }
            else {
                L = Mid;
            }
        }
        Console.WriteLine(R);
    }

    // X以下にできるかを返す
    static bool CanAchieve(int pX)
    {
        var CloneBList = new List<int>();
        CloneBList.AddRange(mBList);
        CloneBList.Add(pX);
        CloneBList.Sort();

        int UB = mAArr.GetUpperBound(0);
        for (int I = 0; I <= UB; I++) {
            if (mAArr[I] > CloneBList[I]) {
                return false;
            }
        }
        return true;
    }
}

解説

答えを二分探索してます。
10の9乗 * 2 は Int型に収まるので
Int型を使用してます。