はまやんはまやんはまやん

hamayanhamayan's blog

最長の数列 [yukicoder 390]

問題

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

N個の集合 S={x1,x2,...,xN} がある。
以下の条件を満たす「良い」数列の中で最も長い数列の長さは?

数列を (a1,a2,...,aM) とする
1. ∀i(1 <= i <= M) ai ∈ S
2. ∀i(1 <= i <= M - 1) 「ai < ai+1」かつ「ai+1はaiの倍数」

1 <= N <= 10^5
1 <= xi <= 10^6
xi != xj (1 <= i < j <= N)

考察

1. 組合せ問題の解き方は色々あるが…
2. 数学的に解く -> 倍数チェックがあるのでダメかも
3. DPで解く -> 解けそうかな…??
4. そもそも求めたい数列が最長増加部分列みたいな雰囲気あるから、DPで考えてみる
5. xiの数が微妙に小さいぞ???
6. xiの数は全て異なるぞ???
7. xiの数を要素に持ってDPを考えてみよう

い け る や ん

8. まず集合をソートしておく(ソートできるものは全てソートすると解法が分かったりする)
9. 以下のようにdpを計算する

dp[10^6+1]
dp[i]=(集合Sに含まれる1~iの数を使って作れる良い数列の中で最も長い数列の長さ)

xiの約数を {d1,d2,...,dn-1,dn=xi} とする
dp[xi] = max(dp[d1], dp[d2], ... , dp[dn-1])

10. ぶっちゃけ計算量計算できないんですけど、間に合いそうな感じある

実装

http://yukicoder.me/submissions/102232

int N;
int x[101010];
//-----------------------------------------------------------------
typedef long long ll;
vector<ll> enumdiv(ll n) {
    vector<ll> S;
    for (ll i = 1; i*i <= n; i++) if (n%i == 0) { S.push_back(i); if (i*i != n) S.push_back(n / i); }
    sort(S.begin(), S.end());
    return S;
}
//-----------------------------------------------------------------
int dp[1010101];
int main() {
    scanf("%d", &N);
    rep(i, 0, N) scanf("%d", &x[i]);
    sort(x, x + N);

    rep(i, 0, N) dp[x[i]] = 1;
    
    rep(i, 1, 1000001) if(dp[i]){
        auto v = enumdiv(i);
        for (int j : v) if(j != i) dp[i] = max(dp[i], dp[j] + 1);
    }
    
    int ans = 0;
    rep(i, 0, N) ans = max(ans, dp[x[i]]);
    cout << ans << endl;
}