hamayanhamayan https://blog.hatena.ne.jp/hamayanhamayan/ はまやんはまやんはまやん https://blog.hamayanhamayan.com/ 競技プログラミング https://yukicoder.me/problems/no/979 前提知識 LIS 解説 https://yukicoder.me/submissions/424709 LISに問題設定が似ているので、LISに寄せた感じで考えてみる。 DPっぽくやっていく。 dp[i][x] := i番目まで考え終わっていて、末尾の値がxである最長列の長さ dp[i+1][x]の更新を考えると、考えるべきはdp[i][y]（yはxの約数、かつxより小さい）である。 yは約数であるので、約数列挙してもO(sqrt(x))しかかからない。 これは間に合いそうな気がする。 あとは、DPテーブルがとても大きく… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fblog.hamayanhamayan.com%2Fentry%2F2020%2F02%2F01%2F131548" title="Longest Divisor Sequence [yukicoder 979] - はまやんはまやんはまやん" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2020-02-01 13:15:48 rich https://blog.hamayanhamayan.com/entry/2020/02/01/131548 1.0 100%