AtCoder Beginner Contest 120

結果

　22分59秒(1WA)で全完。140位だった。WAなければ100位以内という前回と同じパターンか。

A問題

　はい。

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

int main() {
    ll A, B, C;
    cin >> A >> B >> C;
    cout << min(B / A, C) << endl;
}

B問題

　どうあがいても全探索で殴ればいいいつものB問題。最初小さい方から数えて番目を出力するコードを書いてしまっていた。初期化もmin(A, B)で良いのに無駄にmax(A, B)から探し始めてしまった。

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

int main() {
    ll A, B, K;
    cin >> A >> B >> K;

    ll num = 0;
    for (ll i = max(A, B); ; i--) {
        if (A % i == 0 && B % i == 0) {
            if (++num == K) {
                cout << i << endl;
                return 0;
            }
        }
    }
}

C問題

　最初「赤赤」または「青青」が消せるのかと誤読していた。どちらにしてもスタックに詰みながら貪欲に考えていけばなんかできそうと証明のないままに提出してAC。

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

int main() {
    string S;
    cin >> S;

    ll ans = 0;
    stack<char> st;
    for (char c : S) {
        if (st.empty() || st.top() == c) {
            st.push(c);
        } else {
            st.pop();
            ans += 2;
        }
    }

    cout << ans << endl;
}

D問題

　パッと見で後ろから考えるやつだろうなぁと思うし、サイズが求められるUnionFindを使えばそれでいけそうと考える。ライブラリで持ってるUnionFindはサイズが求められないやつだったので少し改良して提出。そこそこWAが出る。同じときは答えを減らしてはいけないんだった。修正して投げてAC。典型感が強い。

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

class UnionFind {
public:
    UnionFind(ll n) {
        par_.resize(n, -1);
    }

    //根を求める
    ll find(ll x) {
        return (par_[x] < 0 ? x : par_[x] = find(par_[x]));
    }

    //xとyの属する集合を併合
    void unite(ll x, ll y) {
        x = find(x);
        y = find(y);
        if (x == y) {
            return;
        }
        par_[x] += par_[y];
        par_[y] = x;
    }

    //xが属する集合のサイズを取得
    ll size(ll x) {
        return -par_[find(x)];
    }

    //xとyが同じ集合に属するか否かを判定
    bool same(ll x, ll y) {
        return (find(x) == find(y));
    }
private:
    vector<ll> par_;
};

int main() {
    ll N, M;
    cin >> N >> M;
    vector<ll> A(M), B(M);
    for (ll i = 0; i < M; i++) {
        cin >> A[i] >> B[i];
        A[i]--;
        B[i]--;
    }

    UnionFind uf(N);
    vector<ll> ans(M);
    ans[M - 1] = N * (N - 1) / 2;
    for (ll i = M - 1; i > 0; i--) {
        if (uf.same(A[i], B[i])) {
            ans[i - 1] = ans[i];
            continue;
        }
        ll size1 = uf.size(A[i]);
        ll size2 = uf.size(B[i]);
        ans[i - 1] = ans[i] - size1 * size2;
        uf.unite(A[i], B[i]);
    }

    for (auto a : ans) {
        cout << a << endl;
    }
}