第9回PAST L 嘘つきな生徒たち

問題へのリンク

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 10");
            WillReturn.Add("7 5 10 3 2");
            //1
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("5 10");
            WillReturn.Add("9 8 7 7 5");
            //1
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("11 1000000000");
            WillReturn.Add("0 1 10 100 1000 10000 100000 1000000 10000000 100000000 1000000000");
            //10
        }
        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();
    }

    static void Main()
    {
        List<string> InputList = GetInputList();
        long Result = Solve(InputList);
        Console.WriteLine(Result);
    }

    static long Solve(List<string> pInputList)
    {
        long[] wkArr = GetSplitArr(pInputList[0]);
        long P = wkArr[1];

        long[] AArr = GetSplitArr(pInputList[1]);
        long UB = AArr.GetUpperBound(0);

        // 値の下限以外を設定
        long CurrJyougen = P;
        var ValueInfoList = new List<ValueInfoDef>();
        for (long I = 0; I <= UB; I++) {
            var WillAdd = new ValueInfoDef();
            WillAdd.CurrVal = AArr[I];
            WillAdd.Jyougen = CurrJyougen--;
            WillAdd.Distance = AArr[I] + I;
            ValueInfoList.Add(WillAdd);
        }

        // 値の下限を設定
        long CurrKagen = 0;
        for (long I = UB; 0 <= I; I--) {
            ValueInfoList[(int)I].Kagen = CurrKagen++;
        }

        // 値が範囲内な要素のみ残す
        ValueInfoList = ValueInfoList.FindAll(pX => pX.Kagen <= pX.CurrVal && pX.CurrVal <= pX.Jyougen);

        // LISを求める用のList
        var LisList = ValueInfoList.Select(pX => pX.Distance).ToList();
        LisList.Reverse();

        long LISLength = ClassDeriveNonStrictLISLength.DeriveLength(LisList);

        return AArr.Length - LISLength;
    }

    class ValueInfoDef
    {
        internal long CurrVal;  // 初期値
        internal long Kagen;    // 値の下限(狭義単調減少とする必要条件)
        internal long Jyougen;  // 値の上限(狭義単調減少とする必要条件)
        internal long Distance; // 直交座標での原点からのマンハッタン距離
    }
}

#region ClassDeriveNonStrictLISLength
// LIS(広義単調増加)の長さを返す
internal class ClassDeriveNonStrictLISLength
{
    // 引数 long型の列挙
    // 戻り値 LISの長さ
    internal static long DeriveLength(IEnumerable<long> pEnum)
    {
        // LISの最終値の最小値[LISの長さ] なDP表
        var DPSortedList = new SortedList<long, long>();

        foreach (long EachVal in pEnum) {
            if (DPSortedList.Count == 0) {
                DPSortedList[1] = EachVal;
                continue;
            }
            long UpsertKeyInd = ExecNibunhou(DPSortedList, EachVal);

            long CurrUB = DPSortedList.Count - 1;
            var Keys = DPSortedList.Keys;

            // 更新する位置によって分岐
            if (UpsertKeyInd <= CurrUB) {
                DPSortedList[Keys[(int)UpsertKeyInd]] = EachVal;
            }
            else {
                long PrevKey = Keys[(int)CurrUB];
                DPSortedList[PrevKey + 1] = EachVal;
            }
        }

        if (DPSortedList.Count == 0) {
            return 0;
        }
        int UB = DPSortedList.Count - 1;
        return DPSortedList.Keys[UB];
    }

    // 二分法で、引数の値を設定する、キーの配列の添字を返す
    private static long ExecNibunhou(SortedList<long, long> pDPSortedList, long pTargetVal)
    {
        long UB = pDPSortedList.Count - 1;
        var Keys = pDPSortedList.Keys;

        // 最小値未満の場合
        if (pTargetVal < pDPSortedList[Keys[0]]) {
            return 0;
        }

        // 最大値以上の場合
        if (pTargetVal >= pDPSortedList[Keys[(int)UB]]) {
            return UB + 1;
        }

        long L = 0, R = UB;

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

            if (pTargetVal < pDPSortedList[Keys[(int)Mid]]) {
                R = Mid;
            }
            else {
                L = Mid;
            }
        }
        return R;
    }
}
#endregion

解説

まず、真だとすると矛盾が発生するものは偽だと分かります。
具体例1 真だとすると、後続で1点ずつ減っていったときに最後の人の得点がマイナスになる場合。
具体例2 真だとすると、前方に1点ずつ増やしていったときに最初の人の得点が上限を超える場合。

次に、LISを考えるのですが、LISに入れなかった値も考える必要があるため、
直交座標での原点(0,0)からの距離を図示してみます。

6789ABCDE
56789ABCD
456789ABC
3456789AB
23456789A
123456789
012345678

たとえば(0,5)の値は5で、6や7にLISの数列として遷移してしまうと、
LISに入れなかった、生徒を含めて狭義単調減少な数列を作れなくなってしまいます。
逆に、(0,5)からは、5以下にLISの数列として遷移すれば、大丈夫だと分かります。

以上により、下記の手順で解くことができます。
手順1 真とすると矛盾する要素をremoveする
手順2 原点からの距離を求め、右から左に向かって、広義単調増加なLISの長さを求める