第111回【Python】最長増加連続部分列、【連続列】最長減少連続部分列
現在取り組んでいるのは、paiza ラーニング問題集「DP メニュー」になります。
https://paiza.jp/worksはじめに
猫とキャンプと野球観戦と AWS が大好きな旦那、LeoSaki です。モフモフしたい。
Python をゼロから勉強してみよう、のコーナー 111 回目です。
人間の記憶というのは曖昧なもので、「最初がどんな状態だったか」を記録していないと、現在の状態が変わっているかどうかの判断をつけるのが難しくなります。毎日見ているのに、たった一つのステータスの変化を見逃してしまい余計な手がかかってしまう、ということもありえます。
それでは、今日も頑張ってみようと思います。
最長増加連続部分列
https://paiza.jp/works/mondai/dp_primer/dp_primer_lis_contin...n 人が横一列に並んでいます。左から i 番目の人を人 i と呼ぶことにします。人 i の身長は a_i [cm]です。
人 l ,人 l+1, … , 人 r からなる区間 [l, r] について、すべての l ≦ i < r に対して a_i ≦ a_{i+1} が成り立っているとき、区間 [l, r] は背の順であると呼ぶことにします。また、区間 [l, r] の長さを r-l+1 とします。
背の順であるような区間のうち、最長であるものの長さを出力してください。
(ヒント)
元の問題を解くために、部分問題としてどのような問題を考えればよいでしょうか。
dp[n] を、人 n が右端となっているような背の順区間のうち、最長であるような区間の長さとしてみましょう。dp[1] ~ dp[k-1] が既に求まっているとして、dp[k] がどうなるかを考えてみましょう。dp[k-1] に注目すると、dp[k-1] は人 k-1 を右端とする背の順区間の長さですから、もし a_{k-1} ≦ a_k なら、その区間の右端に人 k をくっつけることで新しく長さ dp[k-1]+1 の背の順区間を作ることができ、この区間の長さは人 k を右端として持つ背の順区間のうち最長であることがわかります。逆に、もし a_{k-1} ＞ a_k なら、人 k が右端となるような背の順区間は人 k のみからなる長さ1の区間しか存在しないことがわかります。
以上の考察により、dp[k-1] と dp[k] の関係が明らかになりました。自信のある人は自分で漸化式を立ててみましょう。以下の疑似コードに従って、自分の得意な言語で実装してみましょう。
dp[1] <- 1
for i = 2 to n
if a[i-1] <= a[i] then
dp[i] <- dp[i-1]+1
else
dp[i] <- 1
print max({dp[1], ... ,dp[n]})n
a_1
a_2
...
a_n・ 1行目に、横一列に並んでいる人の人数 n が与えられます。
・ 続く n 行のうち i 行目では、人 i の身長 a_i が与えられます。
すべてのテストケースにおいて、以下の条件をみたします。
・ 1 ≦ n ≦ 200,000
・ 100 ≦ a_i ≦ 200
入力例
5
160
178
170
190
190出力例
3比較した結果を新たなリストに出力していく。結構よくあるパターンだと思います。
Python
n = int(input())
A = [int(input()) for _ in range(n)]
dp = [1] * n
for i in range(1,n):
if A[i-1] <= A[i]:
dp[i] = dp[i-1] + 1
else:
dp[i] = 1
print(max(dp))VBA
N = Cells(1, 1)
Dim A() As Integer, dp() As Long
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)
If A(i - 1) <= A(i) Then
dp(i) = dp(i - 1) + 1
Else
dp(i) = 1
End If
Next
Debug.Print Application.WorksheetFunction.Max(dp)【連続列】最長減少連続部分列
https://paiza.jp/works/mondai/dp_primer/dp_primer_lis_contin...n 人が横一列に並んでいます。左から i 番目の人を人 i と呼ぶことにします。人 i の身長は a_i [cm]です。
人 l ,人 l+1, … , 人 r からなる区間 [l, r] について、すべての l ≦ i < r に対して a_i ≧ a_{i+1} が成り立っているとき、区間 [l, r] は逆背の順であると呼ぶことにします。また、区間 [l, r] の長さを r-l+1 とします。
逆背の順であるような区間のうち、最長であるものの長さを出力してください。
n
a_1
a_2
...
a_n・ 1行目に、横一列に並んでいる人の人数 n が与えられます。
・ 続く n 行のうち i 行目では、人 i の身長 a_i が与えられます。
すべてのテストケースにおいて、以下の条件をみたします。
・ 1 ≦ n ≦ 200,000
・ 100 ≦ a_i ≦ 200
入力例
5
187
192
115
108
109出力例
3単純に前問の逆、でしょうか。
Python
n = int(input())
A = [int(input()) for _ in range(n)]
dp = [1] * n
for i in range(1,n):
if A[i-1] >= A[i]:
dp[i] = dp[i-1] + 1
else:
dp[i] = 1
print(max(dp))VBA
N = Cells(1, 1)
Dim A() As Integer, dp() As Long
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)
If A(i - 1) >= A(i) Then
dp(i) = dp(i - 1) + 1
Else
dp(i) = 1
End If
Next
Debug.Print Application.WorksheetFunction.Max(dp)最後に
今回取り組んだ問題での N の条件は 200,000 人となっています。paiza で用意されているテストケースには境界値のものもあるので試してみると良いと思います。VBA で試してみても、なかなかの速度で解答を出すことができていました。（これは、ローカルマシンの性能もあると思うので一概には言えないと思いますが）
この問題に取り組みながら考えていたのですが、やり方を知らなかった場合、どんな風に解いていただろう。前の値と今の値を比較して、条件に合えばカウントを +1 をする。違えば、max 値を格納する変数とカウントを比較して大きい方を max 値を格納する変数に格納する。カウントをリセットする。なかなか手順が増えて大変そうです。
引き続き、よろしくお願いいたします！