Codeforces Round #686 (Div. 3)

codeforces.com

A. Special Permutation

偶数なら先頭から2個ずつペアにしてswapする
奇数の場合も同様にして最後の1要素だけ適当にswapさせる
$ n, 1, 2, 3, ..., n-1 $で良かったね
提出コード

void solve(){
    int n;
    cin >> n;
    vector<int> a(n);
    iota(a.begin(), a.end(), 1);
    for(int i=0;i<n-1;i+=2) swap(a[i], a[i+1]);
    if(n > 2) swap(a[n-1], a[n-3]);
    REP(i,n) cout << a[i] << " ";
    cout << endl;
}

B. Unique Bid Auction

問題文の通りに一人だけが選んだ数の中で最小のものを求めて、そのindexを出力する
提出コード

void solve(){
    int n;
    cin >> n;
    vector<int> a(n);
    vector<int> cnt(n+1);
    REP(i,n){
        cin >> a[i];
        cnt[a[i]]++;
    }
    int ans = -1;
    int mi = -1;
    for(int i=1;i<=n;i++){
        if(cnt[i] == 1){
            mi = i;
            break;
        }
    }
    REP(i,n) if(a[i] == mi) ans = i + 1;
    cout << ans << endl;
}

C. Sequence Transformation

いい実装方法思いつかなかった
RLEして各値ごとにindexを見る
直前に見たindexを$ pre=0 $ として$ pre \lt idx_{cur} $ならその間の区間は消す必要がある
また、最後に見たindexが数列の最後の要素でなければその区間も消す必要がある
提出コード

void solve(){
    int n;
    cin >> n;
    vector<int> a(n);
    REP(i,n) cin >> a[i];
    auto res = runLengthEncoding(a);
    vector<int> cnt(n+1);
    vector<vector<int>> idx(n);
    REP(i,res.size()) idx[res[i].first-1].emplace_back(i);
    int m = res.size();
    int ans = INF;
    REP(i,n){
        int tmp = 0;
        int pre = 0;
        if(idx[i].size() == 0) continue;
        REP(j,idx[i].size()){
            if(idx[i][j] > pre) tmp++;
            pre = idx[i][j];
        }
        if(pre < m-1) tmp++;
        // dumps(i, tmp);
        chmin(ans, tmp);
    }
    cout << ans << endl;
}

D. Number into Sequence

素因数分解をする
条件を満たす数列の長さの最大は、$ N $の各素因数の数のmax - 1になる
そのため最も多い素因数の数 - 1個その素因数を出力し、残った素因数の積に1つその素因数をかけてあげれば条件を満たす
提出コード

void solve(){
    ll n;
    cin >> n;
    auto res = prime_factorize(n);
    ll ma = 0;
    ll prime = 0;
    for(auto [p, cnt] : res) if(chmax(ma, cnt)) prime = p;
    ll rest = n;
    while(rest % prime == 0) rest /= prime;
    cout << ma << endl;
    REP(i,ma-1) cout << prime << " ";
    cout << rest * prime << endl;
}

E. Number of Simple Paths

$ n $頂点 $ n $辺の連結な無向グラフなので、木に辺を1本足したグラフになる
これは必ずサイクルを1個含み、そのサイクルから毛が生えたようなグラフになる（なもりグラフ？）
毛の生えた部分に注目するとサイクルのどの頂点から生えてるかでグループ分け出来る
そのグループ間の中のパスは必ず一意になる
逆に異なるグループ間のパスだとサイクルを右・左回りのどちらを通るかで2通りになる
そのため、全体のパスの個数から各グループごとに重複分を引いてあげればいい
サイクルは1個しかないのでdfsとかで十分
提出コード

void solve(){
    ll n;
    cin >> n;
    vector<vector<int>> g(n);
    REP(i,n){
        int u, v;
        cin >> u >> v;
        g[--u].emplace_back(--v);
        g[v].emplace_back(u);
    }
    vector<int> v;
    int pos = -1;
    vector<bool> seen(n), finished(n);
    auto dfs = [&](auto && self, int cur, int par = -1){
        seen[cur] = true;
        v.emplace_back(cur);
        for(auto nv : g[cur]){
            if(nv == par) continue;
            if(finished[nv]) continue;
            if(seen[nv] and !finished[nv]){
                pos = nv;
                return;
            }
            self(self, nv, cur);
            if(pos != -1) return;
        }
        v.pop_back();
        finished[cur] = true;
    };
    dfs(dfs, 0);
    vector<ll> cnt(n);
    queue<tuple<int, int, int>> q;
    vector<bool> used(n);
    set<int> cycle;
    while(!v.empty()){
        int cur = v.back();
        cycle.insert(cur);
        v.pop_back();
        if(cur == pos) break;
    }
    for(auto x : cycle){
        q.emplace(x, -1, x);
        used[x] = true;
    }
    while(!q.empty()){
        auto [cur, par, group] = q.front(); q.pop();
        cnt[group]++;
        for(auto nv : g[cur]){
            if(nv == par) continue;
            if(used[nv]) continue;
            q.emplace(nv, cur, group);
        }
    }
    ll ans = n * (n - 1);
    for(auto c : cnt) if(c > 0) ans -= c * (c - 1) / 2;
    cout << ans << endl;
}