第23回PAST J オフィス

問題へのリンク

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("1 10");
            WillReturn.Add("5 30");
            WillReturn.Add("10 15");
            WillReturn.Add("20 40");
            //2 3 2 1
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("10");
            WillReturn.Add("33553 130683");
            WillReturn.Add("93150 198918");
            WillReturn.Add("44559 198032");
            WillReturn.Add("87304 140783");
            WillReturn.Add("58113 161838");
            WillReturn.Add("858 74380");
            WillReturn.Add("39597 150815");
            WillReturn.Add("2425 149780");
            WillReturn.Add("8298 10367");
            WillReturn.Add("37788 184869");
            //8 7 8 7 8 7 8 9 2 8
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static long[] GetSplitArr(string pStr)
    {
        return (pStr == "" ? new string[0] : pStr.Split(' ')).Select(pX => long.Parse(pX)).ToArray();
    }

    struct RangeInfoDef
    {
        internal long RangeSta;
        internal long RangeEnd;
    }
    static List<RangeInfoDef> mRangeInfoList = new List<RangeInfoDef>();

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

        long[] wkArr = { };
        Action<string> SplitAct = (pStr) => wkArr = GetSplitArr(pStr);

        foreach (string EachStr in InputList.Skip(1)) {
            SplitAct(EachStr);
            RangeInfoDef WillAdd;
            WillAdd.RangeSta = wkArr[0];
            WillAdd.RangeEnd = wkArr[1];
            mRangeInfoList.Add(WillAdd);
        }

        long[] RangeStaArr = mRangeInfoList.Select(pX => pX.RangeSta).ToArray();
        long[] RangeEndArr = mRangeInfoList.Select(pX => pX.RangeEnd).ToArray();
        Array.Sort(RangeStaArr);
        Array.Sort(RangeEndArr);

        var AnswerList = new List<long>();
        foreach (RangeInfoDef EachRangeInfo in mRangeInfoList) {
            long Cnt1 = GetArrRangeValueCnt.GetLessStrictCnt(RangeEndArr, EachRangeInfo.RangeSta);
            long Cnt2 = GetArrRangeValueCnt.GetMoreStrictCnt(RangeStaArr, EachRangeInfo.RangeEnd);
            AnswerList.Add(N - 1 - Cnt1 - Cnt2);
        }

        Console.WriteLine(LongEnumJoin(" ", AnswerList));
    }

    // セパレータとLong型の列挙を引数として、結合したstringを返す
    static string LongEnumJoin(string pSeparater, IEnumerable<long> pEnum)
    {
        string[] StrArr = Array.ConvertAll(pEnum.ToArray(), pX => pX.ToString());
        return string.Join(pSeparater, StrArr);
    }
}

#region GetArrRangeValueCnt
// {昇順にソートされた配列,Min,Max}を引数とし、
// Min以上Max以下な値の個数を返す
internal class GetArrRangeValueCnt
{
    // 機能01 Min以上な値の個数を返す
    static internal long GetMoreOrEqualCnt(long[] pSortedArr, long pMinVal)
    {
        long ResultInd = ExecNibunhou_LowerBound(pMinVal, pSortedArr);

        if (ResultInd == -1) return 0;
        return pSortedArr.GetUpperBound(0) - ResultInd + 1;
    }

    // 機能02 Min超えな値の個数を返す
    static internal long GetMoreStrictCnt(long[] pSortedArr, long pMinVal)
    {
        long ResultInd = ExecNibunhou_UpperBound(pMinVal, pSortedArr);

        if (ResultInd == -1) return 0;
        return pSortedArr.GetUpperBound(0) - ResultInd + 1;
    }

    // 機能03 Max以下な値の個数を返す
    static internal long GetLessOrEqualCnt(long[] pSortedArr, long pMaxVal)
    {
        long ResultInd = ExecNibunhou_LowerOrEqual_Max(pMaxVal, pSortedArr);

        if (ResultInd == -1) return 0;
        return ResultInd + 1;
    }

    // 機能04 Max未満な値の個数を返す
    static internal long GetLessStrictCnt(long[] pSortedArr, long pMaxVal)
    {
        long ResultInd = ExecNibunhou_LowerMax(pMaxVal, pSortedArr);

        if (ResultInd == -1) return 0;
        return ResultInd + 1;
    }

    // 機能05 Min以上Max以下な値の個数を返す
    static internal long GetRangeCnt(long[] pSortedArr, long pMinVal, long pMaxVal)
    {
        if (pMinVal > pMaxVal) {
            throw new Exception("pMinVal > pMaxVal");
        }

        long ResultInd1 = ExecNibunhou_LowerBound(pMinVal, pSortedArr);
        if (ResultInd1 == -1) return 0;

        long ResultInd2 = ExecNibunhou_LowerOrEqual_Max(pMaxVal, pSortedArr);
        if (ResultInd2 == -1) return 0;

        return ResultInd2 - ResultInd1 + 1;
    }

    // 二分法で、Val以上で最小の値を持つ、添字を返す
    static private long ExecNibunhou_LowerBound(long pVal, long[] pArr)
    {
        if (pArr.Length == 0) return -1;

        // 最後の要素がVal未満の特殊ケース
        if (pVal > pArr.Last()) {
            return -1;
        }
        // 最初の要素がVal以上の特殊ケース
        if (pVal <= pArr[0]) {
            return 0;
        }

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

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

            if (pArr[Mid] >= pVal) {
                R = Mid;
            }
            else {
                L = Mid;
            }
        }
        return R;
    }

    // 二分法で、Val超えで最小の値を持つ、添字を返す
    static private long ExecNibunhou_UpperBound(long pVal, long[] pArr)
    {
        if (pArr.Length == 0) return -1;

        // 最後の要素がVal以下の特殊ケース
        if (pVal >= pArr.Last()) {
            return -1;
        }
        // 最初の要素がVal超えの特殊ケース
        if (pVal < pArr[0]) {
            return 0;
        }

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

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

            if (pArr[Mid] > pVal) {
                R = Mid;
            }
            else {
                L = Mid;
            }
        }
        return R;
    }

    // 二分法で、Val以下で最大の値を持つ、添字を返す
    static private long ExecNibunhou_LowerOrEqual_Max(long pVal, long[] pArr)
    {
        if (pArr.Length == 0) return -1;

        // 最後の要素がVal以下の特殊ケース
        if (pVal >= pArr.Last()) {
            return pArr.GetUpperBound(0);
        }
        // 最初の要素がVal超えの特殊ケース
        if (pVal < pArr[0]) {
            return -1;
        }

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

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

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

    // 二分法で、Val未満で最大の値を持つ、添字を返す
    static private long ExecNibunhou_LowerMax(long pVal, long[] pArr)
    {
        if (pArr.Length == 0) return -1;

        // 最後の要素がVal未満の特殊ケース
        if (pVal > pArr.Last()) {
            return pArr.GetUpperBound(0);
        }
        // 最初の要素がVal以上の特殊ケース
        if (pVal <= pArr[0]) {
            return -1;
        }

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

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

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

解説

数直線で考えると
AとBが出会う条件は、下記です。

Bの退社する以前にAが出社
かつ
Bが出社後にAが退社

これを不等式で表現します。
EndB >= StaA かつ StaB <= EndA
これの否定条件に、ドモルガンの法則を適用します。
EndB < StaA または StaB > EndA
向きを統一して
EndB < StaA または EndA < StaB

数直線で考えると、このORの2つの条件を両方とも満たすことはありえないので、
二分探索で補集合の要素数を高速に数えれば、解が分かります。