Codeforces Round #641 (Div. 2) 参加記

コンテストへのリンク

参加しました。結果は以下です。 メモリオーバーで悲しかったです。考察はできていたので余計。

A

問題へのリンク

2回目以降は必ず2を足すので。

B

問題へのリンク

解説

昇順にしたいので、後ろにindexを持ってソートする。その後indexの約数からもらうDP。自分と同じ値からは遷移させないように注意。

実装

template<typename T>
vector<T> divisor(T N) {
    vector<T> res;
    for(T i = 1; i * i <= N; i++){
        if(N % i == 0){
            res.push_back(i);
            if(i * i != N)res.push_back(N / i);
        }
    }
    sort(res.begin(), res.end());
    return res;
}


void solve(){
    int N;
    cin >> N;
    vector<ll> v(N);
    vector<l_l> vidx;
    rep(i,N){
        cin >> v[i];
        vidx.emplace_back(v[i], i+1);
    }
    sort(all(vidx));
    vector<ll> cnt(N+1, -1);
    rep(i,N){
        ll idx = vidx[i].second;
        if(idx == 1){
            cnt[idx] = 1;
            continue;
        }
        auto _divisor = divisor(idx);
        cnt[idx] = 1;
        for(auto &p: _divisor){
            if(cnt[p] == -1)continue;
            if(v[p-1] == v[idx-1])continue;
            chmax(cnt[idx], cnt[p]+1);
        }
    }
    ll ans = *max_element(all(cnt));
    cout << ans << endl;
}
int main() {
    int t;
    cin >> t;
    while(t--) solve();
}

C

問題概要

問題へのリンク

全ペアの最小公倍数の最大公約数を求めよ。

解説

素因数ごとに分けて考える。ペアを取ったときの最小値が答え。最小値は、含まれていない値二つを取れるなら0、含まれてないのが一個しかないならその次の値、全部に含まれてるなら最小2個のペアをとる。 本番ではメモリオーバーで、理由は簡単で含まれないやつをして保存しようとしたため。0はなくてもさっきの情報はわかる。

実装

template<typename T> 
map<T,int> factorize(T x){
    map<T,int> mp;
    for (T i = 2; i*i <= x; i++){
        while (x%i == 0) {
            x /= i;
            mp[i]++;
        }
        if (x == 1) break;
    }
    if (x != 1) mp[x]++;
    return mp;
}

ll power_pow(ll a, ll n) {
    ll res = 1;
    while (n > 0) {
        if (n & 1) res = res * a;
        a = a * a;
        n >>= 1;
    }
    return res;
}
int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(20);

    int N;
    cin >> N;
    vector<int> a(N);
    rep(i,N)cin >> a[i];

    vvec<int> b(200010, vec<int>());
    rep(i,N){
        auto v = factorize(a[i]);
        for(auto &p: v){
            b[p.first].push_back(p.second);
        }
    }
    ll ans = 1;
    rep(i,200010){
        sort(all(b[i]));
        if(b[i].size() <= N-2)continue;
        if(b[i].size() == N-1){
            ans *= power_pow(i, b[i][0]);
        }
        if(b[i].size() == N){
            ans *= power_pow(i, b[i][1]);
        }
    }
    cout << ans << endl;
}

D

問題へのリンク

面白そうだったから考察したけど誤読してました。そのうち記事にします。

-> 記事にしました coonevo.hatenablog.com

お疲れ様でした。