接着剤の精進日記

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

トップ > AtCoderBeginnerContest > AtCoder Beginner Contest 239（ABC239）

AtCoder Beginner Contest 239（ABC239）

AtCoderBeginnerContest AtCoderBeginnerContest239 ABC ABC239

atcoder.jp

A - Horizon

問題文の数式をそのまま求める

提出コード

void solve(){
    ll x;
    cin >> x;
    printf("%.12lf\n", sqrt(x * (x + 12800000)));
}

B - Integer Division

負の数のときの処理に気をつける

提出コード

void solve(){
    ll X;
    cin >> X;
    cout << floor_div(X, 10) << endl;
}

C - Knight Fork

問題文の図にある通り、あり得る箇所は $ (x1, y1) $ の周り8通りと $ (x2, y2) $ の周り8通りなのでこれを全探索し、一致する座標があるかどうかを判定する

提出コード

void solve(){
    ll x1, x2, y1, y2;
    cin >> x1 >> y1 >> x2 >> y2;
    int dx[8] = {1, 2, 2, 1, -1, -2, -2, -1};
    int dy[8] = {2, 1, -1, -2,  2, 1, -1, -2};
    bool ok = false;
    REP(i,8){
        ll nx1 = x1 + dx[i];
        ll ny1 = y1 + dy[i];
        REP(j,8){
            ll nx2 = x2 + dx[j];
            ll ny2 = y2 + dy[j];
            if(nx1 == nx2 and ny1 == ny2) ok = true;
        }
    }
    cout << (ok ? "Yes" : "No") << endl;
}

D - Prime Sum Game

高橋くんが選んだ数字に対し、青木くんが選べるどの数字を使っても素数にできないとき、高橋くんはその数を選べばいい
そのような数字がないときは青木くんが必ず勝つ

提出コード

void solve(){
    int A, B, C, D;
    cin >> A >> B >> C >> D;
    SieveOfEratosthenes<int> sieve(222);
    bool ok = false;
    for(int i=A;i<=B;i++){
        bool ok2 = true;
        for(int j=C;j<=D;j++){
            if(sieve.is_prime[i+j]) ok2 = false;
        }
        ok |= ok2;
    }
    cout << (ok ? "Takahashi" : "Aoki") << endl;
}

E - Subtree K-th Max

ある頂点において、その頂点の部分木に含まれる頂点に書かれている数字の大きい順に20個求めればいい
DFSをし、葉のほうから順に上位20件の数字を更新していけばいい

提出コード

void solve(){
    int N, Q;
    cin >> N >> Q;
    vector<ll> X(N);
    REP(i,N) cin >> X[i];
    vector<vector<int>> g(N);
    REP(i,N-1){
        int a, b;
        cin >> a >> b;
        --a, --b;
        g[a].emplace_back(b);
        g[b].emplace_back(a);
    }
    vector<multiset<int>> dp(N);
    REP(i,N) dp[i].insert(X[i]);
    vector<int> idx(N);
    iota(ALL(idx), 0);
    auto dfs = [&](auto && self, int v, int par) -> void{
        for(auto nv : g[v]){
            if(nv == par) continue;
            self(self, nv, v);
            for(auto &x : dp[nv]){
                if(dp[v].size() < 20) dp[v].insert(x);
                else{
                    dp[v].insert(x);
                    dp[v].erase(dp[v].begin());
                }
            }
        }
        return;
    };
    dfs(dfs, 0, -1);

    REP(i,Q){
        int v, k;
        cin >> v >> k;
        --v, --k;
        for(auto itr=dp[v].rbegin();itr!=dp[v].rend();itr++){
            if(k == 0){
                cout << *itr << endl;
                break;
            }
            k--;
        }
    }
}

F - Construct Highway

$ \sum D_i = 2(N-1) $ の時の場合を考える
連結成分ごとに残りいくつの辺を繋げることができるかを管理する
このとき、残り2以上の連結成分があれば残り1の連結成分との辺を結んでいく
最終的に残り1の連結成分がちょうど2つ残っていれば条件を満たす木を構築することができる

提出コード

void solve(){
    int N, M;
    cin >> N >> M;
    vector<int> D(N);
    REP(i,N) cin >> D[i];
    UnionFind uf(N);
    REP(i,M){
        int a, b;
        cin >> a >> b;
        --a, --b;
        D[a]--, D[b]--;
        uf.unite(a, b);
    }
    vector<vector<int>> v(N);
    REP(i,N){
        if(D[i] < 0){
            cout << -1 << endl;
            return;
        }
        REP(j,D[i]) v[uf.root(i)].emplace_back(i);
    }
    vector<int> cnt1;
    vector<vector<int>> cnt2;
    REP(i,N){
        if(v[i].size() == 1) cnt1.emplace_back(v[i][0]);
        else if(v[i].size() > 1) cnt2.emplace_back(v[i]);
    }
    vector<pair<int, int>> ans;
    for(auto vec : cnt2){
        REP(i,(int)vec.size()-1){
            if(cnt1.empty()){
                cout << -1 << endl;
                return;
            }
            uf.unite(vec[i], cnt1.back());
            ans.emplace_back(vec[i], cnt1.back());
            cnt1.pop_back();
        }
        cnt1.emplace_back(vec.back());
    }
    if(cnt1.size() != 2){
        cout << -1 << endl;
        return;
    }
    uf.unite(cnt1[0], cnt1[1]);
    ans.emplace_back(cnt1[0], cnt1[1]);
    if(uf.size(0) != N){
        cout << -1 << endl;
        return;
    }
    for(auto [a, b] : ans) cout << a+1 << " " << b+1 << endl;
}