VK Cup 2015 - Finals, online mirror

はい。
http://codeforces.com/contest/566

F. Clique in the Divisibility Graph

ざっくりと大意

・n個の頂点のグラフは\(a_i\)と\(a_j\)が割り切れる関係の時に辺で接続されている？
・最も接続が多いのがいくつか？？

方針のようなもの

・たぶん、ひたすら約数の個数を調べるしか無い気がするけどよくわからない

C++11

#include<bits/stdc++.h>
#include<vector>
#include<list>
#include<stack>
#include<queue>
#include<algorithm>
using namespace std;

const int MAXN=1000001;
int a[MAXN];
int b[MAXN];
int dp[MAXN];
int n;

int dfs(int cur){
    if(b[cur]==0){
        return 0;
    }
    int& ret=dp[cur];
    if(ret>0){
        return ret;
    }
    ret=0;
    for(int i=2;i*cur<MAXN;i++){
        ret=max(ret,dfs(i*cur));
    }
    ret+=b[cur];
    return ret;
}

int main(){
    for(int i=0;i<MAXN;i++){
        a[i]=0;
        b[i]=0;
        dp[i]=0;
    }
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        scanf("%d",&a[i]);
        b[a[i]]++;
    }
    int ans=0;
    for(int i=1;i<MAXN;i++){
        if(dp[i]==0){
            ans=max(ans,dfs(i));
        }
    }
    printf("%d\n",ans);
    return 0;
}

パクった
http://mayokoex.hatenablog.com/entry/2015/08/07/124913
aには問題の入力の数列を入れる。bには数列aの中にpという数がいくつあるかを入れる。(pythonなら連想配列使うかも。時間厳しいのでアレですけど)。dpにはよくわからん。。。