TopCoder Single Round Match 779

　Easyを落として緑に落ちた。

　TopCoderのレートはあまり気にしていないつもりだったけど、緑に落ちたのは結構ショックだったので、もっと真剣にやらないと、と反省しました。
　それに、このEasyは通さなくてはいけない問題だったので、そこも反省。

Div1 Easy ArraySorting

　数列Aの要素をいくつか変更し、Aを広義単調増加にしたい。

　変更する要素の個数が最小になるようにし、辞書順最小のAを求める。

　まあ、LISを復元する問題といって良いと思う。

　LISに関する理解がちゃんとしていれば解けたはずなので、解けなかったのはLISの理解ができていなかったということでしょう。

　「辞書順最小」というのに惑わされるけど、「DP[i]で、長さiのLISの最終要素の最小値」を取る、という方法（たとえば、ここの説明が分かりやすいと思う）でLISを求める際に、復元用のリストを用意していれば、自然と辞書順最小のものが求められる。

　この問題も、yukicoder contest 237のNo.992 最長増加部分列の数え上げも、それほど捻った出題じゃないのに意外と難しく感じてしまうのは、LISのアルゴリズム自体がそもそも簡単じゃないからだと思う。

　とはいえ、基本的なアルゴリズムなのだから、ちゃんと身に着けておかないと……。

　以下、ACコード。

import bisect

class ArraySorting():
    def arraySort(self, A):
        N=len(A)
        DP=[1<<31]*N
        fr=[-1]*N # 復元用のリスト

        for i in range(N):
            a=A[i]
            pos=bisect.bisect_right(DP,a)
            DP[pos]=a
            if DP[pos-1]==1<<31:
                fr[i]=1
            else:
                fr[i]=DP[pos-1]

        ANS=0 # LISの長さ
        for i in range(N):
            if DP[i]!=1<<31:
                ANS=i
                LASTV=DP[i]

        NEXT=LASTV

        B=[]

        for i in range(N-1,-1,-1):
            a=A[i]
            if a==NEXT:
                B.append(a)
                NEXT=fr[i]
                
            else:
                B.append(NEXT)

        return B[::-1]