ABC006D トランプ挿入ソート

この記事で使うアルゴリズム

動的計画法

はじめに

カテゴリー競プロ初中級者100問では、Qiitaにて@e869120さんがレッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編：目指せ水色コーダー！】としてまとめられている100問をPythonで解いています。

全問題の一覧はこちらです

問題

https://atcoder.jp/contests/abc006/tasks/abc006_4

この問題は動的計画法を用いて解くことができます。

方針

• 最長増加部分列(LIS)を求める
  • 動的計画法により実装する
• N - 最長増加部分列の長さが解になる。

最長増加部分列(LIS)とは

• ある数列から順番を変えずに任意の要素を取り出し新たな数列を作ることができます。
  これを部分列と呼びます。
• 単調増加な数列を増加列と呼びます。

すなわち、ある数列の最長増加部分列とは、その数列の増加部分列のうち最も長いものの長さを表します。

ポイント

動的計画法により求める

部分増加列の長さ	0	1	2	…	N
列の右端の最小値	0	INF	INF	…	INF

具体的に、入力例1について考えてみよう。以下のようにカードが並んでいる。

6 # 枚数
1
3
5
2
4
6

1. 初期化

   部分増加列の長さ	0	1	2	3	4	5	6
   列の右端の最小値	0	INF	INF	INF	INF	INF	INF

2. 1を挿入すべき場所を考える

   部分増加列の長さ	0	1	2	3	4	5	6
   列の右端の最小値	0	1	INF	INF	INF	INF	INF

3. 3を挿入すべき場所を考える

   部分増加列の長さ	0	1	2	3	4	5	6
   列の右端の最小値	0	1	3	INF	INF	INF	INF

4. 5を挿入すべき場所を考える

   部分増加列の長さ	0	1	2	3	4	5	6
   列の右端の最小値	0	1	3	5	INF	INF	INF

5. 2を挿入すべき場所を考える

   部分増加列の長さ	0	1	2	3	4	5	6
   列の右端の最小値	0	1	2	5	INF	INF	INF

6. 4を挿入すべき場所を考える

   部分増加列の長さ	0	1	2	3	4	5	6
   列の右端の最小値	0	1	2	4	INF	INF	INF

7. 6を挿入すべき場所を考える

   部分増加列の長さ	0	1	2	3	4	5	6
   列の右端の最小値	0	1	2	4	6	INF	INF

列の右端の最小値の（INFを除いた）最大値は6であり、その時の部分列の長さは4である。これをカードの枚数Nから引いて、解は2となる

コード（50点）

N = int(input())
cards = []
for n in range(N):
    cards.append(int(input()))
INF = 10010
lis = [INF] * (N+1) # 列の右端の最小値
lis[0] = 0
ans = 0
for n in range(N):
    for m in range(n+1): #  無駄にINFの領域を探索する必要はない
        if lis[m] < cards[n] and cards[n] < lis[m+1]: # 今回は同じ値のカードはない
            lis[m+1] = cards[n]
            ans = max(ans, m+1)
            break # 更新できたらループを抜けて良い
print(N-ans)

満点解法

上記のアルゴリズムは計算量がO(n^2)であるが、さらに高速化ができる。

列の右端の最小値が増加列であるということを利用して、二分探索を行えば良い。

コード（100点）

import bisect
N = int(input())
cards = []
for n in range(N):
    cards.append(int(input()))
INF = 100010
lis = [INF]* (N+1)
lis[0] = 0
ans = 0
for n in range(N):
    i = bisect.bisect(lis, cards[n]) # 二分探索
    lis[i] = cards[n]
    ans = max(ans, i)
print(N-ans)

記事情報

• 投稿日：2020年4月18日
• 最終更新日：2020年5月8日