接着剤の精進日記

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

トップ > AtCoderBeginnerContest160 > AtCoder Beginner Contest 160（ABC160）

AtCoder Beginner Contest 160（ABC160）

AtCoderBeginnerContest160 AtCoderBeginnerContest ABC160 ABC

atcoder.jp

ねんがんの青パフォーマンスをてにいれたぞ

A - Coffee

S[2] == S[3] && S[4] == S[5] を判定
提出コード

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    string S;
    cin >> S;
    if(S[2] == S[3] && S[4] == S[5]) cout << "Yes" << endl;
    else cout << "No" << endl;
}

B - Golden Coins

500円硬貨を取れるだけ取って残りから5円硬貨を取れるだけ取る
提出コード

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll X;
    cin >> X;
    ll ans = 0;
    ans += X / 500 * 1000;
    X -= X / 500 * 500;
    cout << ans + X / 5 * 5 << endl;
}

C - Traveling Salesman around Lake

これ難しいかなーって思ったけど7400人以上通すんだね
環状のものを考えるときはとりあえず2周分取っておくと扱いやすくなる
そうすると時計回りと反時計回りでの答えの最小を求めてあげればいい
提出コード

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int K, N;
    cin >> K >> N;
    vector<ll> A(2*N);
    REP(i,N) cin >> A[i];
    for(int i=N;i<2*N;i++) A[i] = A[i-N] + K;

    ll ans = LINF;
    for(int i=0;i<N;i++){
        chmin(ans, A[i+N-1] - A[i]);
    }
    for(int i=2*N-1;i>=N;i--){
        chmin(ans, A[i] - A[i-N+1]);
    }
    cout << ans << endl;
}

D - Line++

これぱっと見難しい
よくよく制約を見ると\mathcal{O}(N^2 logN)が通りそう（ちょっとlogが怖いかな？）
なので毎回dijkstraをして距離を数え上げていけばいい
提出コード

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N, X, Y;
    cin >> N >> X >> Y;
    --X, --Y;
    Dijkstra<int> d(N, INF);
    d.make_edge(X, Y, 1);
    d.make_edge(Y, X, 1);
    REP(i,N-1){
        d.make_edge(i, i+1, 1);
        d.make_edge(i+1, i, 1);
    }
    vector<int> ans(N);
    REP(i,N-1){
        d.solve(i);
        for(int j=i+1;j<N;j++) ans[d.cost[j]]++;
    }
    for(int i=1;i<N;i++) cout << ans[i] << endl;
}

E - Red and Green Apples

貪欲法でいいんだけどちょっと怖いよね
まず赤いリンゴも緑のリンゴも上位X, Y個以外は見なくていい
その集合にC個の無色のリンゴを加えたものから上位X + Y個を取ることを考える
この時、どのようにとっても無色のリンゴを適切に塗ることで赤いリンゴがX個、緑のリンゴがY個を達成できる
本番はpriority_queue使ったけどこう考えるとソートするだけでいいね（まったく考えてなかったけどこれ頭いい）
提出コード

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int X, Y, A, B, C;
    cin >> X >> Y >> A >> B >> C;
    vector<int> p(A), q(B), r(C);
    REP(i,A) cin >> p[i];
    REP(i,B) cin >> q[i];
    REP(i,C) cin >> r[i];
    sort(p.rbegin(), p.rend());
    sort(q.rbegin(), q.rend());
    priority_queue<int, vector<int>, greater<int>> pq1, pq2;
    REP(i,X) pq1.push(p[i]);
    REP(i,Y) pq2.push(q[i]);

    REP(i,C){
        int pt = pq1.top();
        int qt = pq2.top();
        if(pt < qt){
            if(pt < r[i]){
                pq1.pop();
                pq1.push(r[i]);
            }
        }
        else{
            if(qt < r[i]){
                pq2.pop();
                pq2.push(r[i]);
            }
        }
    }
    ll ans = 0;
    while(!pq1.empty()){
        ans += pq1.top(); pq1.pop();
    }
    while(!pq2.empty()){
        ans += pq2.top(); pq2.pop();
    }
    cout << ans << endl;
}

F - Distributing Integers

見た目がRerooting（全方位DP）
なんですが、そもそもの数え上げパートがわからずお手上げ
アルメリアさんの記事がわかりやすくて、ボールを並べることを考えた時、その並べ方の数というふうに考える
そうすると、適当な頂点を根としたときの場合の数がdfsで求められる
後はその情報を元にもう一度dfsをして、遷移させていくことで答えが求められる（難しい）

betrue12.hateblo.jp

提出コード

vector<vector<int>> G;
int sz[202020];
mint dp[202020];
mint fac[202020];
mint ans[202020];
int N;

void dfs1(int v, int par){
    dp[v] = 1;
    for(auto nv : G[v]){
        if(nv == par) continue;
        dfs1(nv, v);
        sz[v] += sz[nv];
        dp[v] *= dp[nv] * fac[sz[v]] / fac[sz[v] - sz[nv]] / fac[sz[nv]];
    }
    sz[v]++;
}

void dfs2(int v, int par, mint val){
    ans[v] = dp[v] * val * fac[N-1] / fac[N-sz[v]] / fac[sz[v]-1];
    for(auto nv : G[v]){
        if(nv == par) continue;
        mint next = ans[v] / dp[nv] / (fac[N-1] / fac[sz[nv]] / fac[N-sz[nv]-1]);
        dfs2(nv, v, next);
    }
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> N;
    G.resize(N);
    REP(i,N-1){
        int a, b;
        cin >> a >> b;
        --a, --b;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    fac[0] = 1;
    for(int i=1;i<202020;i++) fac[i] = fac[i-1] * i;
    dfs1(0, -1);
    dfs2(0, -1, 1);
    REP(i,N) cout << ans[i] << endl;
}

おわりに

ようやくABCで青パフォが取れて嬉しい
最近よくRerootingを見る気がする？Rerootingってすぐわかったけどそもそも数え上げができなかったのがだめ（数学力さん…）
青パフォ取れて青になれる未来がちょっと見えたので頑張りたいね（青パフォ以上取れないと青になれないため…）