AtCoder Beginner Contest 226（ABC226）

atcoder.jp

Bondo416さんのAtCoder Beginner Contest 226での成績：1284位
パフォーマンス：1303相当
レーティング：1536→1515 (-21) :(#AtCoder #ABC226 https://t.co/ErJkOICLbB

— ボンド@競プロ (@bond_cmprog) November 7, 2021

A - Round decimals

文字列で受け取って、小数点第一位で場合分け

提出コード

void solve(){
    string s;
    cin >> s;
    int cur = 0;
    REP(i,s.size()){
        if(s[i] == '.'){
            if(s[i+1] >= '5') cur++;
            cout << cur << endl;
            return;
        }
        else{
            cur = cur * 10 + (s[i] - '0');
        }
    }
}

B - Counting Arrays

vectorをsetに入れる

提出コード

void solve(){
    int N;
    cin >> N;
    set<vector<int>> st;
    REP(i,N){
        int l;
        cin >> l;
        vector<int> a;
        REP(j,l){
            int num;
            cin >> num;
            a.emplace_back(num);
        }
        st.insert(a);
    }
    cout << st.size() << endl;
}

C - Martial artist

逆からDFSで必要なスキルをすべて取得したときのコストを求める

提出コード

void solve(){
    int N;
    cin >> N;
    vector<int> T(N);
    vector<vector<int>> A(N);
    REP(i,N){
        cin >> T[i];
        int K;
        cin >> K;
        A[i].resize(K);
        REP(j,K){
            cin >> A[i][j];
            --A[i][j];
        }
    }
    ll ans = 0;
    REP(i,N) reverse(ALL(A[i]));
    vector<int> used(N);
    auto dfs = [&](auto && self, int cur) -> void{
        ans += T[cur];
        for(auto a : A[cur]){
            if(!used[a]) self(self, a);
        }
        used[cur] = true;
    };
    dfs(dfs, N-1);
    cout << ans << endl;
}

D - Teleportation

任意の2点間の間の傾きを求める
その傾きがユニークなものの総数が答え

提出コード

void solve(){
    int N;
    cin >> N;
    vector<int> x(N), y(N);
    REP(i,N) cin >> x[i] >> y[i];
    set<pair<int, int>> st;
    REP(i,N) REP(j,N) if(i != j){
        int x1 = x[j] - x[i], y1 = y[j] - y[i];
        int g1 = gcd(abs(x1), abs(y1));
        x1 /= g1, y1 /= g1;
        if(x1 == 0) y1 = 1;
        if(y1 == 0) x1 = 1;
        if(x1 < 0) x1 *= -1, y1 *= -1;
        st.insert({x1, y1});
    }
    cout << 2 * (int)st.size() << endl;
}

E - Just one

連結成分の個数を $ sz $ とすると $ 2^{sz} $ が答えになる
各連結成分において、頂点の個数と辺の個数が一致している必要があり、そうでない場合は -1となる

提出コード

void solve(){
    int N, M;
    cin >> N >> M;
    vector<int> u(M), v(M);
    REP(i,M){
        cin >> u[i] >> v[i];
        --u[i], --v[i];
    }
    UnionFind uf(N);
    REP(i,M){
        if(uf.issame(u[i], v[i])) continue;
        uf.unite(u[i], v[i]);
    }
    vector<int> cnt_v(N), cnt_e(N);
    set<int> st;
    REP(i,N){
        st.insert(uf.root(i));
        cnt_v[uf.root(i)]++;
    }
    REP(i,M) cnt_e[uf.root(u[i])]++;
    REP(i,N){
        if(cnt_v[i] != cnt_e[i]){
            cout << 0 << endl;
            return;
        }
    }
    cout << modpow(mint(2), (int)st.size()) << endl;
}