ARC123-B Increasing Triples

問題へのリンク

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("5");
            WillReturn.Add("9 6 14 1 8");
            WillReturn.Add("2 10 3 12 11");
            WillReturn.Add("15 13 5 7 4");
            //3
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("1");
            WillReturn.Add("10");
            WillReturn.Add("20");
            WillReturn.Add("30");
            //1
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("3");
            WillReturn.Add("1 1 1");
            WillReturn.Add("1 1 2");
            WillReturn.Add("2 2 2");
            //0
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

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

        long[] AArr = InputList[1].Split(' ').Select(pX => long.Parse(pX)).ToArray();
        long[] BArr = InputList[2].Split(' ').Select(pX => long.Parse(pX)).ToArray();
        long[] CArr = InputList[3].Split(' ').Select(pX => long.Parse(pX)).ToArray();

        Array.Sort(AArr);
        Array.Sort(BArr);
        Array.Sort(CArr);

        long UB = AArr.GetUpperBound(0);

        long LB_B = 0;
        long LB_C = 0;

        long Answer = 0;
        foreach (long EachA in AArr) {
            long BInd = ExecNibunhou(EachA, BArr, LB_B);
            if (BInd == -1) break;

            long BVal = BArr[BInd];
            long CInd = ExecNibunhou(BVal, CArr, LB_C);
            if (CInd == -1) break;

            Answer++;

            // LBを進める
            LB_B = BInd + 1;
            if (LB_B > UB) break;

            LB_C = CInd + 1;
            if (LB_C > UB) break;
        }
        Console.WriteLine(Answer);
    }

    // 二分法で引数より大きい最小の添字を返す
    static long ExecNibunhou(long pK, long[] pArr, long pLB)
    {
        // 最後の要素がK以下の特殊ケース
        if (pK >= pArr.Last()) {
            return -1;
        }
        // 最初の要素がより大きい特殊ケース
        if (pK < pArr[pLB]) {
            return pLB;
        }

        long L = pLB;
        long R = pArr.GetUpperBound(0);

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

            if (pArr[Mid] <= pK) {
                L = Mid;
            }
            else {
                R = Mid;
            }
        }
        return R;
    }
}

解説

昇順にソート済の下記の3つの配列を考えます。

1 6  8  9 14
2 3 10 12 11
4 5  7 13 15

Aを全探索し、Aより大きい最小のB、Bより大きい最小のC
を二分法で求めてます。

使用済の配列Bと配列Cの要素は、
配列のLower_Boundを持つことで管理してます。