ABC134-E Sequence Decomposing

問題へのリンク

C#のソース(Listクラスを使う方法)

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("2");
            WillReturn.Add("1");
            WillReturn.Add("4");
            WillReturn.Add("5");
            WillReturn.Add("3");
            //2
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("4");
            WillReturn.Add("0");
            WillReturn.Add("0");
            WillReturn.Add("0");
            WillReturn.Add("0");
            //4
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();
        int[] AArr = InputList.Skip(1).Select(pX => int.Parse(pX)).ToArray();

        var DescList = new List<int>();
        DescList.Add(AArr[0]);
        foreach (int EachInt in AArr.Skip(1)) {
            int ResultInd = ExecNibunhou(EachInt, DescList);
            if (ResultInd == DescList.Count()) {
                DescList.Add(EachInt);
            }
            else {
                DescList[ResultInd] = EachInt;
            }
        }
        Console.WriteLine(DescList.Count);
    }

    // 二分法で、引数未満で最大の値を持つ、添字を返す
    static int ExecNibunhou(int pVal, List<int> pList)
    {
        // 最後の要素がVal以上の特殊ケース
        if (pVal <= pList.Last()) {
            return pList.Count;
        }
        // 最初の要素がVal未満の特殊ケース
        if (pVal > pList[0]) {
            return 0;
        }

        int L = 0;
        int R = pList.Count - 1;

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

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

C#のソース(RBSTでC++のMultiSetを模倣する方法)

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("2");
            WillReturn.Add("1");
            WillReturn.Add("4");
            WillReturn.Add("5");
            WillReturn.Add("3");
            //2
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("4");
            WillReturn.Add("0");
            WillReturn.Add("0");
            WillReturn.Add("0");
            WillReturn.Add("0");
            //4
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();
        int[] AArr = InputList.Skip(1).Select(pX => int.Parse(pX)).ToArray();

        int Result = Solve(AArr);
        Console.WriteLine(Result);
    }

    static int Solve(int[] pAArr)
    {
        var Ins_CPP_MultiSet = new CPP_MultiSet<int>();
        Ins_CPP_MultiSet.Insert(pAArr[0]);

        foreach (int EachInt in pAArr.Skip(1)) {
            int ResultInd = ExecNibunhou(Ins_CPP_MultiSet, EachInt);
            if (ResultInd == -1) {
                Ins_CPP_MultiSet.Insert(EachInt);
            }
            else {
                Ins_CPP_MultiSet.Remove(Ins_CPP_MultiSet[ResultInd]);
                Ins_CPP_MultiSet.Insert(EachInt);
            }
        }
        return Ins_CPP_MultiSet.Count();
    }

    // 二分法で、引数未満で最大の値を持つ、添字を返す
    static int ExecNibunhou(CPP_MultiSet<int> pIns_CPP_MultiSet, int pTargetVal)
    {
        int UB = pIns_CPP_MultiSet.Count() - 1;

        // 最初の要素がVal以上の特殊ケース
        if (pTargetVal <= pIns_CPP_MultiSet[0]) {
            return -1;
        }

        // 最後の要素がVal未満の特殊ケース
        if (pTargetVal > pIns_CPP_MultiSet[UB]) {
            return UB;
        }

        int L = 0;
        int R = UB;

        while (L + 1 < R) {
            int Mid = (L + R) / 2;
            if (pIns_CPP_MultiSet[Mid] < pTargetVal) {
                L = Mid;
            }
            else {
                R = Mid;
            }
        }
        return L;
    }
}

#region CPP_Set_MultiSet
// Self-Balancing Binary Search Tree
// (using Randamized BST)
internal class SB_BinarySearchTree<T> where T : IComparable
{
    internal class Node
    {
        internal T Value;
        internal Node LChild;
        internal Node RChild;
        internal int Count; // 部分木のサイズ

        internal Node(T v)
        {
            Value = v;
            Count = 1;
        }
    }

    static Random _rnd = new Random();

    internal static int Count(Node t)
    {
        return t == null ? 0 : t.Count;
    }

    static Node Update(Node t)
    {
        t.Count = Count(t.LChild) + Count(t.RChild) + 1;
        return t;
    }

    internal static Node Merge(Node l, Node r)
    {
        if (l == null || r == null) return l == null ? r : l;

        if ((double)Count(l) / (double)(Count(l) + Count(r)) > _rnd.NextDouble()) {
            l.RChild = Merge(l.RChild, r);
            return Update(l);
        }
        r.LChild = Merge(l, r.LChild);
        return Update(r);
    }

    // C#4.0のTuppleクラスもどき
    internal struct CS4_Tupple_Node
    {
        internal Node mItem1;
        internal Node mItem2;

        internal CS4_Tupple_Node(Node pItem1, Node pItem2)
        {
            mItem1 = pItem1;
            mItem2 = pItem2;
        }
    }

    // split as [0, k), [k, n)
    internal static CS4_Tupple_Node Split(Node t, int k)
    {
        if (t == null) return new CS4_Tupple_Node(null, null);
        if (k <= Count(t.LChild)) {
            CS4_Tupple_Node s = Split(t.LChild, k);
            t.LChild = s.mItem2;
            return new CS4_Tupple_Node(s.mItem1, Update(t));
        }
        else {
            CS4_Tupple_Node s = Split(t.RChild, k - Count(t.LChild) - 1);
            t.RChild = s.mItem1;
            return new CS4_Tupple_Node(Update(t), s.mItem2);
        }
    }

    internal static Node Remove(Node t, T v)
    {
        if (Find(t, v) == null) return t;
        return RemoveAt(t, LowerBound(t, v));
    }

    internal static Node RemoveAt(Node t, int k)
    {
        CS4_Tupple_Node s = Split(t, k);
        CS4_Tupple_Node s2 = Split(s.mItem2, 1);
        return Merge(s.mItem1, s2.mItem2);
    }

    internal static bool Contains(Node t, T v)
    {
        return Find(t, v) != null;
    }

    internal static Node Find(Node t, T v)
    {
        while (t != null) {
            int cmp = t.Value.CompareTo(v);
            if (cmp > 0) t = t.LChild;
            else if (cmp < 0) t = t.RChild;
            else break;
        }
        return t;
    }

    internal static Node FindByIndex(Node t, int idx)
    {
        if (t == null) return null;

        int currentIdx = Count(t) - Count(t.RChild) - 1;
        while (t != null) {
            if (currentIdx == idx) return t;
            if (currentIdx > idx) {
                t = t.LChild;
                currentIdx -= (Count(t == null ? null : t.RChild) + 1);
            }
            else {
                t = t.RChild;
                currentIdx += (Count(t == null ? null : t.LChild) + 1);
            }
        }
        return null;
    }

    internal static int UpperBound(Node t, T v)
    {
        Node torg = t;
        if (t == null) return -1;

        int ret = int.MaxValue;
        int idx = Count(t) - Count(t.RChild) - 1;
        while (t != null) {
            int cmp = t.Value.CompareTo(v);

            if (cmp > 0) {
                ret = Math.Min(ret, idx);
                t = t.LChild;
                idx -= (Count(t == null ? null : t.RChild) + 1);
            }
            else if (cmp <= 0) {
                t = t.RChild;
                idx += (Count(t == null ? null : t.LChild) + 1);
            }
        }
        return ret == int.MaxValue ? Count(torg) : ret;
    }

    internal static int LowerBound(Node t, T v)
    {
        Node torg = t;
        if (t == null) return -1;

        int idx = Count(t) - Count(t.RChild) - 1;
        int ret = int.MaxValue;
        while (t != null) {
            int cmp = t.Value.CompareTo(v);
            if (cmp >= 0) {
                if (cmp == 0) ret = Math.Min(ret, idx);
                t = t.LChild;
                if (t == null) ret = Math.Min(ret, idx);
                idx -= t == null ? 0 : (Count(t.RChild) + 1);
            }
            else if (cmp < 0) {
                t = t.RChild;
                idx += (Count(t == null ? null : t.LChild) + 1);
                if (t == null) return idx;
            }
        }
        return ret == int.MaxValue ? Count(torg) : ret;
    }

    internal static Node Insert(Node t, T v)
    {
        int ub = LowerBound(t, v);
        return InsertByIdx(t, ub, v);
    }

    static Node InsertByIdx(Node t, int k, T v)
    {
        CS4_Tupple_Node s = Split(t, k);
        return Merge(Merge(s.mItem1, new Node(v)), s.mItem2);
    }

    internal static IEnumerable<T> EnumerateList(Node t)
    {
        var ret = new List<T>();
        EnumerateList(t, ret);
        return ret;
    }

    static void EnumerateList(Node t, List<T> ret)
    {
        if (t == null) return;
        EnumerateList(t.LChild, ret);
        ret.Add(t.Value);
        EnumerateList(t.RChild, ret);
    }

    internal static IEnumerable<T> EnumerateYield(Node t)
    {
        if (t != null) {
            foreach (var Each in EnumerateYield(t.LChild)) {
                yield return Each;
            }
            yield return t.Value;
            foreach (var Each in EnumerateYield(t.RChild)) {
                yield return Each;
            }
        }
    }
}

// CPP-Like Set
internal class CPP_Set<T> where T : IComparable
{
    protected SB_BinarySearchTree<T>.Node _root;

    // 機能01 インデクサ(0オリジン)
    internal T this[int idx] { get { return ElementAt(idx); } }

    // 機能02 件数を返す
    internal int Count()
    {
        return SB_BinarySearchTree<T>.Count(_root);
    }

    // 機能03 要素を追加
    internal virtual void Insert(T v)
    {
        if (_root == null) _root = new SB_BinarySearchTree<T>.Node(v);
        else {
            if (SB_BinarySearchTree<T>.Find(_root, v) != null) return;
            _root = SB_BinarySearchTree<T>.Insert(_root, v);
        }
    }

    // 機能04 全ての要素を削除
    internal void Clear()
    {
        _root = null;
    }

    // 機能05 指定した要素があれば削除
    internal void Remove(T v)
    {
        _root = SB_BinarySearchTree<T>.Remove(_root, v);
    }

    // 機能06 指定した要素の有無を返す
    internal bool Contains(T v)
    {
        return SB_BinarySearchTree<T>.Contains(_root, v);
    }

    // 機能07 インデクサの糖衣構文
    internal T ElementAt(int k)
    {
        var node = SB_BinarySearchTree<T>.FindByIndex(_root, k);
        if (node == null) throw new IndexOutOfRangeException();
        return node.Value;
    }

    // 機能08 指定した値の件数を返す
    internal int Count(T v)
    {
        return SB_BinarySearchTree<T>.UpperBound(_root, v) -
               SB_BinarySearchTree<T>.LowerBound(_root, v);
    }

    // 機能09 引数以上の最小添字を返す
    internal int LowerBound(T v)
    {
        return SB_BinarySearchTree<T>.LowerBound(_root, v);
    }

    // 機能10 引数超えの最小添字を返す
    internal int UpperBound(T v)
    {
        return SB_BinarySearchTree<T>.UpperBound(_root, v);
    }

    // C#4.0のTuppleクラスもどき
    internal struct CS4_Tupple_Int
    {
        internal int mItem1;
        internal int mItem2;

        internal CS4_Tupple_Int(int pItem1, int pItem2)
        {
            mItem1 = pItem1;
            mItem2 = pItem2;
        }
    }

    // 機能11 引数に等しい範囲の下限と上限を返す
    internal CS4_Tupple_Int EqualRange(T v)
    {
        if (!Contains(v)) return new CS4_Tupple_Int(-1, -1);
        return new CS4_Tupple_Int(SB_BinarySearchTree<T>.LowerBound(_root, v),
                                  SB_BinarySearchTree<T>.UpperBound(_root, v) - 1);
    }

    // 機能12 Listを作って返す
    internal List<T> ToList()
    {
        return new List<T>(SB_BinarySearchTree<T>.EnumerateList(_root));
    }

    // 機能13 Listでなく列挙を返す
    internal IEnumerable<T> EnumerateYield()
    {
        return SB_BinarySearchTree<T>.EnumerateYield(_root);
    }

    // 機能14 LowerBoundで返したIndが、有効範囲かを判定
    internal bool IsValidInd(int pInd)
    {
        if (pInd < 0) return false;
        if (this.Count() <= pInd) return false;
        return true;
    }
}

// CPP-Like multiset
internal class CPP_MultiSet<T> : CPP_Set<T> where T : IComparable
{
    internal override void Insert(T v)
    {
        if (_root == null) _root = new SB_BinarySearchTree<T>.Node(v);
        else _root = SB_BinarySearchTree<T>.Insert(_root, v);
    }
}
#endregion

解説

LISが最低何個あればいいかという問題なので、
LISごとの最大値を、降順にソートしたListで管理してます。

Listは最後にAddした時の計算量が小さいので
降順にソートしたListとしてます。

平衡二分木で、C++のMultiSetを模倣する方法もあります。