No.390 最長の数列

Quiz

https://yukicoder.me/problems/no/390

Submit

https://yukicoder.me/submissions/19573

解法

• 公式解説の通りではあるが、各dp[i]についてiの約数を列挙してdpを更新してACした
• 配るDPがオススメされていたが、制限時間ギリギリそうな列挙でトライした
• 約数の列挙は計算量がO(N)
• 各 i について列挙を行うのでO(N log N)な気もするが、列挙に時間がかかるのは最後の方だけなのでもっと小さい気もする
• O(N log N)だった場合は、今回はN=10⁶ (値のmax) なので、この見積もりだと10⁹となりTLE
• しかし実際にACしたということは
  • 計算量はO(N log N)より小さい
  • テストケースが全部小さい
• のいずれかであるが、テストケースを見ると前者のようだ

約数列挙

• ミスで同じ約数が入るのを避けるため、今回はsetに入れてみた

set<ll> factorization(ll N){
    set<ll> se;
    for(int i=1; i*i<=N; i++){
        if(N%i==0){
            se.insert(i);
            se.insert(N/i);
        }
    }
    return se;
}