第112回【Python】最長部分増加列、【部分列】最長減少部分列

現在取り組んでいるのは、paiza ラーニング問題集「DP メニュー」になります。

はじめに

猫とキャンプと野球観戦と AWS が大好きな旦那、LeoSaki です。モフモフしたい。

Python をゼロから勉強してみよう、のコーナー 112 回目です。

自己肯定感が低いためになかなか次のステップに進めないことが多いです。まずは今の自分を認めることからということで現状分析を行い、こんなことも出来ないのか、と更に後ろ向きになる悪循環。ポジティブにいきましょう。

それでは、今日も頑張ってみようと思います。

最長部分増加列

n 本の木が横一列に並んでいます。左から i 番目の木を木 i と呼ぶことにします。木 i の高さは a_i [cm] です。
あなたは、何本かの木を伐採することによって、残った木を左から順に見ると高さが単調増加になっているようにしたいと考えています。つまり、残った木を左から 木 k_1, 木 k_2, … , 木 k_m とすると、a_{k_1} < a_{k_2} < ... < a_{k_m} が満たされているようにしたいです。なるべく多くの木が残るように、伐採する木を工夫して選んだとき、伐採されずに残る木の本数が最大でいくつになるか求めてください。
なお、最初から n 本の木が単調増加に並んでいる場合は、1本も伐採しなくてよいものとします。

(ヒント)

まずは問題を整理しましょう。この問題は、添字の部分列 x1 < x2 < ... < xk であって、a_x1 < a_x2 < ... < a_xk を満たしているようなもの (これを、一般に増加部分列と呼びます) のうち、k が最も大きいもの (これを、一般に最長増加部分列 (Longest Increasing Subsequence, LIS) と呼びます) を求めよという問題に言い換えることができます。

dp[k] を、最後が木 k であるような増加部分列のうち最長であるものの長さとしてみましょう。dp[1] ~ dp[k-1] が求まっているとして、dp[k] とこれらの関係はどのようになっているかを考えてみましょう。

少し考えると、1以上 k 未満の i について a_i < a_k が成り立っているとき、最後が木 i であるような増加部分列の最後に木 k をくっつけることで、新しく長さ dp[i] + 1 の増加部分列を作れることがわかります。そして、最後が木 k であるような最長増加部分列は、このようにして作られる部分列のうち最長のものであることがわかります。

これで、dp[1] ~ dp[k-1] と dp[k] の関係が明らかになりました。自信のある方は自分で漸化式を立ててみましょう。以下の疑似コードに従ってあなたの得意な言語で実装してみましょう。

dp[1] <- 1

for i = 2 to n
    dp[i] <- 1  // 木 i のみからなる部分列の長さ
    for j = 1 to i-1
        if a[j] < a[i] then
            dp[i] <- max(dp[i], dp[j]+1)    // 最後が木 j であるような増加部分列の末尾に木 i をくっつける

print max({dp[1], ... ,dp[n]})
n
a_1
a_2
...
a_n

・ 1行目に、横一列に並んでいる木の本数 n が与えられます。
・ 続く n 行のうち i 行目では、木 i の高さ a_i が与えられます。

すべてのテストケースにおいて、以下の条件をみたします。

・ 1 ≦ n ≦ 5,000
・ 1 ≦ a_i ≦ 1,000,000,000
・ a_i ≠ a_j (i ≠ j)

入力例

5
100
102
101
91
199

出力例

3

ちょっと複雑になった。ヒントを読みながら手書きで内容を書いてみると良いと思う。

Python
n = int(input())
A = [int(input()) for _ in range(n)]
dp = [1] * n
for i in range(1,n):
    for j in range(0,i):
        if A[j] < A[i]:
            dp[i] = max(dp[i],dp[j]+1)
print(max(dp))
VBA
N = Cells(1, 1)
Dim A() As Long, dp() As Integer
ReDim A(N - 1)
ReDim dp(N - 1)
For i = 0 To N - 1
    A(i) = Cells(i + 2, 1)
Next
dp(0) = 1
For i = 1 To UBound(dp)
    For j = 0 To i
        If A(j) < A(i) Then
            dp(i) = Application.WorksheetFunction.Max(dp(i), dp(j) + 1)
        End If
    Next
Next
Debug.Print Application.WorksheetFunction.Max(dp)

【部分列】最長減少部分列

n 本の木が横一列に並んでいます。左から i 番目の木を木 i と呼ぶことにします。木 i の高さは a_i [cm] です。

あなたは、何本かの木を伐採することによって、残った木を左から順に見ると高さが単調減少になっているようにしたいと考えています。つまり、残った木を左から 木 k_1, 木 k_2, … , 木 k_m とすると、a_{k_1} > a_{k_2} > ... > a_{k_m} が満たされているようにしたいです。なるべく多くの木が残るように工夫して伐採する木を選んだとき、伐採されずに残る木の本数が最大でいくつになるか求めてください。

なお、最初から n 本の木が単調減少に並んでいる場合は、1本も伐採しなくてよいものとします。

n
a_1
a_2
...
a_n

・ 1行目に、横一列に並んでいる木の本数 n が与えられます。
・ 続く n 行のうち i 行目では、木 i の高さ a_i が与えられます。

すべてのテストケースにおいて、以下の条件をみたします。

・ 1 ≦ n ≦ 5,000
・ 1 ≦ a_i ≦ 1,000,000,000
・ a_i ≠ a_j (i ≠ j)

入力例

5
109
110
108
103
100

出力例

4

前問を逆にするだけだけど、出来れば、きちんと解いてみた方が良いと思う。ちゃんと身になっているか確認するための意味も込めて。

Python
n = int(input())
A = [int(input()) for _ in range(n)]
dp = [1] * n
for i in range(1,n):
    for j in range(0,i):
        if A[j] > A[i]:
            dp[i] = max(dp[i],dp[j]+1)
print(max(dp))
VBA
N = Cells(1, 1)
Dim A() As Long, dp() As Integer
ReDim A(N - 1)
ReDim dp(N - 1)
For i = 0 To N - 1
    A(i) = Cells(i + 2, 1)
Next
dp(0) = 1
For i = 1 To UBound(dp)
    dp(i) = 1
    For j = 0 To i
        If A(j) > A(i) Then
            dp(i) = Application.WorksheetFunction.Max(dp(i), dp(j) + 1)
        End If
    Next
Next
Debug.Print Application.WorksheetFunction.Max(dp)

最後に

なんでこうなるか、を理解したうえでコードを書かないと、次に応用問題に出会ったときに、自力で解くのは難しくなってしまうかも？ 二重ループの中で一体何をしているか。

後は、VBA での型指定ですかね。配列のサイズや要素の最大値を踏まえて型指定する必要がある。全部を variant 型にしてしまうよりも、ちゃんと型指定してあげた方が早いらしいので。

引き続き、よろしくお願いいたします！

Python学習,Python,paiza

Posted by LeoSaki