この記事で使うアルゴリズム
動的計画法
はじめに
カテゴリー競プロ初中級者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
について考えてみよう。以下のようにカードが並んでいる。
1 | 6 # 枚数 |
初期化
部分増加列の長さ 0 1 2 3 4 5 6 列の右端の最小値 0 INF INF INF INF INF INF 1を挿入すべき場所を考える
部分増加列の長さ 0 1 2 3 4 5 6 列の右端の最小値 0 1 INF INF INF INF INF 3を挿入すべき場所を考える
部分増加列の長さ 0 1 2 3 4 5 6 列の右端の最小値 0 1 3 INF INF INF INF 5を挿入すべき場所を考える
部分増加列の長さ 0 1 2 3 4 5 6 列の右端の最小値 0 1 3 5 INF INF INF 2を挿入すべき場所を考える
部分増加列の長さ 0 1 2 3 4 5 6 列の右端の最小値 0 1 2 5 INF INF INF 4を挿入すべき場所を考える
部分増加列の長さ 0 1 2 3 4 5 6 列の右端の最小値 0 1 2 4 INF INF INF 6を挿入すべき場所を考える
部分増加列の長さ 0 1 2 3 4 5 6 列の右端の最小値 0 1 2 4 6 INF INF
列の右端の最小値
の(INFを除いた)最大値は6であり、その時の部分列の長さは4である。これをカードの枚数N
から引いて、解は2
となる
コード(50点)
1 | N = int(input()) |
満点解法
上記のアルゴリズムは計算量がO(n^2)
であるが、さらに高速化ができる。
列の右端の最小値
が増加列であるということを利用して、二分探索を行えば良い。
コード(100点)
1 | import bisect |
記事情報
- 投稿日:2020年4月18日
- 最終更新日:2020年5月8日