yukicoder No390 最長の数列

問題

No.390 最長の数列 - yukicoder

やったこと

まず最初に考えたのは「よい数列」というのはa[i] < a[i + 1](1 <= i <= N - 1)であるので、与えられる集合Sを昇順にして、dp[i][j]:= i番目までの要素を見て、最後に割り切れた要素がj番目の要素である時の良い数列の最大の長さ　としてメモ化再帰をしましたが、
計算量はO(N^2)であるので、TLEでした。

N = int(input())
x = sorted([int(i) for i in input().split()])
dp = [[-1 for j in range(N)] for i in range(N)]
def dfs(i,v):
    if i == N:
        return 0
    if dp[i][v] != -1:
        return dp[i][v]
    ret = 0
    if x[i] % x[v] == 0:
        ret = dfs(i + 1,i) + 1
    ret = max(ret,dfs(i + 1,v))
    dp[i][v] = ret
    return ret
ans = 0
print(dfs(0,0))

次はdp[i] := i番目まで見た時に作ることができる良い最大の数列の長さ　としてDPをしました。
それによって、dpを二次元配列から一次元配列にできた。（もともとあんまり効率良くないことやってたので、当たり前ですね）
i番目の要素ごとにi～1まで見ていくと、だいたいO(N^2)ぐらいなので、これもTLE。

N = int(input())
x = sorted([int(i) for i in input().split()])
dp = [0 for i in range(N)]
for i in range(N):
    for j in range(i,-1,-1):
        if x[i] % x[j] == 0:
            dp[i] = max(dp[i],dp[j] + 1)
print (max(dp))

そして、実際の解法はdp[i] := 値iを良い数列の終端としたときの、構成することが出来る良い数列の最大の長さ
dp[i] = max(dp[j] + 1) 値jは値iの約数、つまりj <= j * 2 <= j * 3 ... j * (i / j) = i

ソースコード

N = int(input())
x = sorted([int(i) for i in input().split()])
M = max(x) + 1
dp = [0] * M
ans = 0
for i in range(N):
	dp[x[i]] = 1
for i in range(N):
	for j in range(x[i] * 2,M,x[i]):
		if dp[j] == 0:
			continue
		dp[j] = max(dp[j],dp[x[i]] + 1)
	ans = max(ans,dp[x[i]])
print (ans)