ABC134E Sequence Decomposing

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

動的計画法

はじめに

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

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

問題

https://atcoder.jp/contests/abc134/tasks/abc134_e

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

この問題を解く前に

この問題はやや発展的な内容です。動的計画法や二分探索に不安がある方は、まずABC006D トランプ挿入ソートを先に解いても良いでしょう。

方針

• 解説pdfの通り数列の後ろから順に考える
• 最長増加部分列問題(LIS)に帰着できます
  • 最長増加部分列問題(LIS)は動的計画法と二分探索により実装できます。

解説

数列の後ろから順に適切な割り当てを考えていきます。そして、この考え方が最長増加部分列問題(LIS)に帰着できることを確認しましょう。

具体的に、入力例1について考えてみよう。

5 # N
2
1
4
5
3

1. 初期化
   以下のような表を更新していきます。（動的計画法）

   色の種類	1	2	3	4
   各色ごとの最小値	INF	INF	INF	INF

2. 3に色を割り当てる

   最初なので、新規に色を作成する（色1）

   色の種類	1	2	3	4
   各色ごとの最小値	3	INF	INF	INF

3. 5に色を割り当てる

   3より大きいので、新規に色を作成する他ない（色2）

   色の種類	1	2	3	4
   各色ごとの最小値	3	5	INF	INF

4. 4に色を割り当てる
   二つの選択肢がある。

   • 新規に色を作成する（色3）

   • 色2の最小値を更新する

     しかし、最小値の更新が可能な場合は明らかに更新を行うべきである。

     色の種類	1	2	3	4
     各色ごとの最小値	3	4	INF	INF

5. 1に色を割り当てる
   更新可能な箇所が複数ある。今後の可能性を広くするために、より小さな値を更新するべきである。
   すなわち1 < 3 < 4であるので、3を1に更新する

   色の種類	1	2	3	4
   各色ごとの最小値	1	4	INF	INF

6. 2に色を割り当てる

   色の種類	1	2	3	4
   各色ごとの最小値	1	2	INF	INF

さて、これまでの操作から色の種類を最小化できたことがわかる。（INFとなっていない色の種類数、すなわち2となる）

各色ごとの最小値は単調増加なので二分探索によって、INFとなっていない色の種類数を求めることができる。

ここまでの処理は、最長増加部分列問題(LIS)と等価である。

コード

import bisect
import sys
input = sys.stdin.readline
N = int(input())
A = []
for n in range(N):
    A.append(int(input()))
A = A[::-1] # 数列の後ろから処理
INF = int(1e+9 + 10)
lis = [INF] * N # 初期化
for n in range(N):
    i = bisect.bisect(lis, A[n]) # 更新すべき最小値
    lis[i] = A[n]
print (bisect.bisect_left(lis, INF)) # `INF`となっていない色の種類数

記事情報

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