Pythonで解く【初中級者が解くべき過去問精選 100 問】(053 - 055 動的計画法：その他)

1. 目的

初中級者が解くべき過去問精選 100 問をPythonで解きます。
すべて解き終わるころに水色になっていることが目標です。

本記事は「053 - 055 動的計画法：その他」です。

2. 総括

「その他」とあるようにこの3問は今までのdpとは少し志向（嗜好？）が違い、dpらしくないdpであると感じました。

3. 本編

053 - 055 動的計画法：その他

053. DPL_1_D - 最長増加部分列

回答

import bisect

n = int(input())
A = [int(input()) for _ in range(n)]
dp = [A[0]]

for i in range(1, n):
    if A[i] > dp[-1]:
        dp.append(A[i])
    else:
        ind = bisect.bisect_left(dp, A[i])
        dp[ind] = A[i]

print(len(dp))

二分探索とDPで解きます。

dp に昇順にAの要素を順に追加していきます。
具体的には、

1. すべてのAの要素A[i]について
2. dpの最後の要素より大きいものはdpに追加し
3. 大きくない場合はdpの中にA[i]以上の数字が存在するので、A[i]で置き換える
4. できあがったdpの長さが答え
   です。

---

054. AtCoder Beginner Contest 006 D - トランプ挿入ソート

回答

import bisect

N = int(input())
C = [int(input()) for _ in range(N)]

dp = [C[0]] # 初期値

for i in range(1, N):
    if C[i] > dp[-1]:
        dp.append(C[i])
    else:
        ind = bisect.bisect_left(dp, C[i])
        dp[ind] = C[i]

print(N - len(dp))

1. DPL_1_D - 最長増加部分列とほぼ同じです。
   違いは最後のprint(N - len(dp))。
   トランプを挿入する必要回数は、トランプの数から最長増加部分列の長さを引いた数になります。

---

055. AtCoder Beginner Contest 134 E - Sequence Decomposing

回答

import bisect
from collections import deque

N = int(input())
A = [int(input()) for _ in range(N)]

dp = deque()
dp.append(A[0])

for i in range(1, N):
    ind = bisect.bisect_left(dp, A[i])

    if ind == 0:
        dp.appendleft(A[i])
    else:
        dp[ind-1] = A[i]

print(len(dp))

上記２つの問題から少しだけ考え方をかえます。
上記２つの問題では、dpの最大値以上の要素をappendしていましたが、
今回は最小値以下の要素をappendleftしていきます。

---