ABC134E Sequence Decomposing

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

動的計画法

はじめに

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

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

問題

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

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

この問題を解く前に

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

方針

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

解説

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

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

1
2
3
4
5
6
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であるので、31に更新する

    色の種類 1 2 3 4
    各色ごとの最小値 1 4 INF INF
  6. 2に色を割り当てる

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

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

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

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

コード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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日