結果

問題 No.390 最長の数列
コンテスト
ユーザー 学ぶマン
提出日時 2025-12-31 12:37:19
言語 PyPy3
(7.3.17)
結果
MLE  
実行時間 -
コード長 1,131 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 336 ms
コンパイル使用メモリ 82,400 KB
実行使用メモリ 694,964 KB
最終ジャッジ日時 2025-12-31 12:37:27
合計ジャッジ時間 7,412 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 2 MLE * 1 -- * 12
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

from collections import deque
N = int(input())
X = list(map(int, input().split()))
limit = max(X)
cnt = [0] * (limit + 1)
for x in X:
    cnt[x] += 1

#G = [list() for _ in range(limit + 1)]
#for i in range(1, (limit//2) + 1):
#    for j in range(2, (limit//i) + 1):
#        G[i].append(i*j)

dist = [-1] * (limit + 1)
for start in range(1, limit + 1):
    if cnt[start] == 0:
        continue
    que = deque()
    que.append(start)
    # 探索したほうが良いか判断
    if dist[start] > cnt[start]:
        continue
    dist[start] = cnt[start]
    while que:
        pos = que.popleft()

        for j in range(2, (limit//pos) + 1):
            nex = pos*j
            if cnt[nex] == 0:
                continue
            # 初訪問のときは cnt を含める
            if dist[nex] == -1:
                dist[nex] = dist[pos] + cnt[nex]
                que.append(nex)
            # 初訪問でない場合、ながくできるなら長くする
            elif dist[nex] - cnt[nex] <= dist[pos]: 
                dist[nex] = dist[pos] + cnt[nex]
                que.append(nex)

ans = max(dist)
print(ans)
0