ABC134 E - Sequence Decomposing

atcoder.jp
解法
貪欲的に考える。
例えば2 1 4 2のような場合、2と1を色aと色bで塗ったとする（これらは異なる色で塗るしかない）。そうすると、次の4は2と同じ色aで塗った方がよいことが分かる。なぜなら、
〇色aの最大値が4、色bの最大値が1
〇色aの最大値が2、色bの最大値が4
前者の方が「状況がよい」ため、つまり次の2を色bで塗れるためである。

より一般的に考えて整数nを塗るときは、色a、色b、色c、・・・のうち、その最大値が整数nより小さいものの中で最大となる色を選んで塗ればよく、整数nより小さな最大値が存在しないときは新しい色で塗ればよい。これを実装するには各色の最大値を要素に持つ配列を用意して二分探索を行えばよい（この配列は常に広義単調減少となるため常に二分探索が可能である）。整数nをすでに存在する色で塗るときにはその色の最大値を表す要素を整数nで更新し、整数nを新しい色で塗るときには配列の末尾に追加する、という操作を順番に行えばよい。

ソースコード（Python3）

from sys import stdin
def main():
    #入力
    readline=stdin.readline
    n=int(readline())
    a=[int(readline()) for _ in range(n)]

    li=[]
    for i in range(n):
        if i==0:
            li.append(a[i])
        else:
            #二分探索
            l=-1
            r=len(li)
            while l<r-1:
                m=(l+r)//2
                if li[m]>=a[i]:
                    l=m
                else:
                    r=m
            if r==len(li):
                li.append(a[i])
            else:
                li[r]=a[i]

    print(len(li))
    
if __name__=="__main__":
    main()