lis
date: 2021-05-18 excerpt: 最長増加部分列(longest increasing sequence)について
最長増加部分列(longest increasing sequence)について
- 連続する文字、数字、tupleなど比較可能な要素で最大でいくつ増え続ける組み合わせがあるかを調べられる
pythonのコード
import bisect
# sample input
N = 7
A = [1, 2, 1, 2, 5, 6, 3]
INF = float('inf')
dp = [INF]*(N+1)
dp[0] = -1
for a in A:
idx = bisect.bisect(dp, a-1) # 最長増加部分列
# idx = bisect.bisect(dp, a) # 広義最長増加部分列
dp[idx] = min(a, dp[idx])
print(dp)
ans = max(i for i in range(N+1) if dp[i] < INF)
例; 広義単調減少が解答になる例
問題
解説
seriesの色の塗り分けは広義単調増加が成立していると計算できる
- 単調増加の逆 ≡ 広義単調減少
- 単調減少の逆 ≡ 広義単調増加
以上の関係性に気づけると解けそう
解答1(難しい例)
N=int(input())
A=[]
for _ in range(N):
A.append(int(input()))
import bisect
INF = float('inf')
dp = [-1]*(N)
for a in A:
# 広義単調減少数列
# 以下の処理は広義単調減少の数を求める
idx = bisect.bisect_left(dp, a)
dp[idx-1] = a
print(N-bisect.bisect_left(dp,0))
解答2(単調増加を反転させて一般化した例)
import bisect
N=int(input())
A=[]
for _ in range(N):
A.append(int(input()))
dp = [float("inf")]*(N+1)
dp[0] = -1
B = [1/(a+1) for a in A] # 逆転させる
for a in B:
# 広義単調減少
# 以下の処理は広義単調の数を求める
idx = bisect.bisect(dp, a)
dp[idx] = min(a, dp[idx])
dp.pop(0)
if dp[-1] != float("inf"):
print(N)
else:
print(sum(1 for x in dp if x < float("inf")))
例; W,Hが定義された箱で何個入れ子にできるか
問題
解説
X,Yの２軸が存在するので、(X, -Y)でソートしたあと、Yに対しての単調増加の最大値を求める
解答
import bisect
N=int(input())
WH=[]
for _ in range(N):
WH.append(list(map(int,input().split())))
WH = [(w,-h, h) for w,h in WH]
WH.sort()
A = [wh[2] for wh in WH]
INF = float('inf')
dp = [INF]*(N+1)
dp[0] = -1
for a in A:
idx = bisect.bisect(dp, a-1) # 最長増加部分列
dp[idx] = min(a, dp[idx])
ans = max(i for i in range(N+1) if dp[i] < INF)
print(ans)
例; 原点と半径を与えられた円がある時、何個最大入れ子にできるか
問題
解説
- 最大の左の円の限界を求めたあと、単調減少になり続ける最大値が答えになる
解答
import bisect
N = int(input())
XR = []
for _ in range(N):
x, r = map(int,input().split())
XR.append( (x-r, x+r) )
XR.sort(reverse=True)
R = [r for l,r in XR]
dp = [float("inf")]*(N)
for a in R:
# 単調減少数列
# 以下の処理は単調減少の数を求める
idx = bisect.bisect_left(dp, a)
dp[idx] = a
print(sum(1 for x in dp if x < float("inf")))
例; bisectでなくてflag管理で求める場合
問題
- AtCoder Grand Contest 013; A - Sorted Arrays 解説
部分部分で成立している単調増加の部分と広義単調減少の部分をflag管理で何個あるかカウントする必要がある
なかなか一人では思いつかずスタックしてしまう
解答
N = int(input())
A = list(map(int, input().split()))
ans = 1
flag = 0
now = A[0]
for i in A[1:]:
if flag == 0 and now > i:
flag = -1
elif flag == 0 and now < i:
flag = 1
elif flag == -1 and now < i:
ans += 1
flag = 0
elif flag == 1 and now > i:
ans += 1
flag = 0
now = i
print(ans)