Codeforces Round #479 (Div. 3) Virtual Contest 参加記

A. Wrong Substraction

間違った引き算アルゴリズムを愚直に実装します。

B. Two-gram

連続する二文字の最頻値を答えます。

C. Less or Equal

X以下の数が個以下になるようなXを求める問題。がコーナーケース。

D. Divide by three, multiply by two

3で割るか、2倍するかの操作でできたある数列を操作された順に並べる問題。 グラフとして表現してDFS。で可能。

グラフとして表現しなくてもできるらしい。

3で割れる回数でソートして出力すればよいらしい。。これは、3で割る操作は、素因数3の数を増やさないという状態から言える。2倍する操作は、素因数3の数が同じときにしか起きないので、3で割れる回数が等しいなら、2倍した操作なので、こちらは昇順である。

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);

    int N;
    cin >> N;
    vector<ll> a(N);
    vector<pair<int, ll>> v;
    for(int i = 0; i < N; i++){
        cin >> a[i];
        int cnt = 0;
        ll tmp = a[i];
        while(tmp % 3 == 0){
            tmp /= 3;
            cnt++;
        }
        v.push_back({-cnt, a[i]});
    }
    sort(v.begin(), v.end());
    for(int i = 0; i < N; i++){
        cout << v[i].second << " ";
    }
    cout << endl;
}

E. Cyclic Components

単純なサイクルがいくつあるかを数える問題。 まず、UnionFindで連結成分に分けて、DFSにより単純なサイクルかどうかを判定。

UnionFindなど使わなくても、DFSで連結成分に分けながら訪問済みからはDFSしないだけで実装できる。確かに。

DFSではなくても、ある連結成分が全て次数2かどうかで判定できるらしい。確かに。

#include <bits/stdc++.h>
using namespace std;
#define rep(i,N) for(int i=0;i<int(N);++i)
using Graph = vector<vector<int>>;
Graph G;

vector<bool> visited;
vector<int> edges;
void dfs(int cur){
    visited[cur] = true;
    edges.push_back(cur);
    for(auto nv: G[cur]){
        if(visited[nv])continue;
        dfs(nv);
    }
    return;
}
int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N, M;
    cin >> N >> M;
    G.resize(N);
    visited.assign(N,false);
    rep(i,M){
        int a,b;
        cin >> a >> b;
        a--, b--;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    int ans = 0;
    rep(i,N){
        edges.clear();
        if(visited[i])continue;
        dfs(i);
        bool ok = true;
        for(auto v: edges){
            if(G[v].size() == 2)continue;
            ok = false;
        }
        if(ok) ans++;
    }
    cout << ans << endl;
}

F. Consecutive Subsequence

単純に左から貪欲に処理していけばよいが、 iが最後のときの連続の最大値

として、前から見ていけばよい。

int main() {

    int N;
    cin >> N;
    vector<int> a(N);
    rep(i,N)cin >> a[i];
    map<int, int> mp;
    for(int i = 0; i < N; i++){
        if(mp[a[i] - 1] == 0)mp[a[i]] = 1;
        else mp[a[i]] = mp[a[i]-1]+1;
    }
    int mx = 0;
    int end = 0;
    for(auto p: mp){
        if(chmax(mx, p.second))end = p.first;
    }
    cout << mx << endl;
    int st = end - mx + 1;
    for(int i = 0; i < N;i++){
        if(a[i] == st){
            cout << i + 1 << " ";
            st++;
        }
    }
    cout << endl;
}

参考

• 公式チュートリアル