[Python] ABC006 D

問題

D – トランプ挿入ソート

最長増加部分列(LIS)の問題です。

以下、Pythonでの最長増加部分列(LIS)の実装について、とても分かりやすく説明しています。

Qiita 最長増加部分列(LIS)の長さを求める

最長増加部分列の長さ取得アルゴリズムLISをpythonで書いてみる

また、Pythonには2分探索が標準ライブラリに用意されています。

bisect — 配列二分法アルゴリズム

回答

import bisect # 二分探索
import sys
# input処理を高速化する
input = sys.stdin.readline


def main():
    N = int(input())
    lst_c = [int(input()) for _ in range(N)]

    dp = [float('inf')]

    for c in lst_c:
        # dpの最後の要素よりcが大きい場合、cを最後に付けて、一つ大きい部分列を作る。
        if c > dp[-1]:
            dp.append(c)
        # 2分探索をしてcより大きいものを上書き
        else:
            pos_insert = bisect.bisect_left(dp, c)
            dp[pos_insert] = c
    
    print(N - len(dp))


main()