接着剤の精進日記

競プロでの精進や研究に関係したことを書いていきます。

トップ > AtCoderBeginnerContest > AtCoder Beginner Contest 259（ABC259）

AtCoder Beginner Contest 259（ABC259）

AtCoderBeginnerContest AtCoderBeginnerContest259 ABC ABC259

atcoder.jp

A - Growth Record

$ X \leq M $ のときは $ T $、そうでない場合は $ T - (X - M) D $

提出コード

void solve(){
    int N, M, X, T, D;
    cin >> N >> M >> X >> T >> D;
    if(X <= M) cout << T << endl;
    else cout << T - (X - M) * D << endl;
}

B - Counterclockwise Rotation

回転行列を考える
$ d $ をラジアンにしたものを $ angle $ とすると、移動先は $ (x, y) = (a cos (angle) - b sin(angle), a sin(angle) + b cos(angle) ) $ となる

提出コード

void solve(){
    int a, b, d;
    cin >> a >> b >> d;
    double angle = d * PI / 180;
    printf("%.12lf %.12lf\n", (double)a * cos(angle) - (double)b * sin(angle), (double)(a) * sin(angle) + (double)(b) * cos(angle));
}

C - XX to XXX

ランレングス圧縮をする
S と Tをランレングス圧縮した配列のサイズが違う場合はNo
同じ場合、$i$ 番目の文字に操作を行って同じ個数にできるかを判定

提出コード

void solve(){
    string S, T;
    cin >> S >> T;
    auto s = runLengthEncoding(S);
    auto t = runLengthEncoding(T);
    if(s.size() != t.size()) cout << "No" << endl;
    else{
        REP(i,s.size()){
            if(s[i].first != t[i].first){
                cout << "No" << endl;
                return;
            }
            else if(s[i].second > t[i].second) {
                cout << "No" << endl;
                return;
            }
            else if(s[i].second == 1 and t[i].second > 1) {
                cout << "No" << endl;
                return;
            }
        }
        cout << "Yes" << endl;
    }
}

D - Circumferences

UnionFindで $ (sx, sy) $ と $ (tx, ty) $ が連結がどうかを判定する
円 $ i, j $ が連結かどうかはその2つの円が共有点を持つかどうかで判定を行う

提出コード

void solve(){
    int N;
    cin >> N;
    ll sx, sy, tx, ty;
    cin >> sx >> sy >> tx >> ty;
    vector<ll> x(N), y(N), r(N);
    REP(i,N) cin >> x[i] >> y[i] >> r[i];
    UnionFind uf(N+2);
    int s = N, t = N + 1;
    REP(i,N) {
        if((sx - x[i]) * (sx - x[i]) + (sy - y[i]) * (sy - y[i]) == r[i] * r[i]) uf.unite(i, s);
        if((tx - x[i]) * (tx - x[i]) + (ty - y[i]) * (ty - y[i]) == r[i] * r[i]) uf.unite(i, t);
    }
    REP(i,N) REP(j,i+1,N){
        ll d = (x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]);
        ll r1 = r[i];
        ll r2 = r[j];
        if(r1 < r2) swap(r1, r2);
        if(d == (r1 + r2) * (r1 + r2)) uf.unite(i, j);
        if((r1 - r2) * (r1 - r2) < d and d < (r1 + r2) * (r1 + r2)) uf.unite(i, j);
        if(d == (r1 - r2) * (r1 - r2)) uf.unite(i, j);
    }
    if(uf.root(s) == uf.root(t)) cout << "Yes" << endl;
    else cout << "No" << endl;
}

E - LCM on Whiteboard

$ a_i = 1 $ としたときに最小公倍数が変わるかどうかを判定する
$ a_i $ が持つ素因数 $ p_{i,j} $ の個数 $ e_{i, j} $ が他の整数 $ a_k (i \neq k) $ が持つ個数の中で最大かつ他に最大の個数を持つ整数がない場合、最小公倍数が変わる可能性がある
$ a_i $ が持つ素因数全てに対し、上記を満たす場合、最小公倍数が変わるので答えとして加算する

提出コード

void solve(){
    int N;
    cin >> N;
    vector<vector<pair<int, int>>> v(N);
    map<int, vector<int>> mp;
    REP(i,N) {
        int m;
        cin >> m;
        v[i].resize(m);
        REP(j,m) {
            int p, e;
            cin >> p >> e;
            v[i][j] = {p, e};
            mp[p].push_back(e);
        }
    }
    for(auto &[k, v] : mp) sort(ALL(v));
    int cnt = 0;
    bool same = false;
    REP(i,N) {
        bool ok = true;
        for(auto &[p, e] : v[i]) {
            int rest = mp[p].end() - lower_bound(ALL(mp[p]), e);
            dumps(i, p, e, rest);
            if(rest <= 1) ok = false;
        }
        if(!ok) cnt++;
        if(ok) same = true;
    }
    cout << cnt + same << endl;
}