AtCoder Beginner Contest 220（ABC220）

atcoder.jp

Bondo416さんのAtCoder Beginner Contest 220での成績：1111位
パフォーマンス：1414相当
レーティング：1475→1469 (-6) :(#AtCoder #ABC220 https://t.co/firyjDIVk0

— ボンド@競プロ (@bond_cmprog) September 26, 2021

A - Find Multiple

for文で探索
提出コード

void solve(){
    int A, B, C;
    cin >> A >> B >> C;
    for(int i=A;i<=B;i++){
        if(i % C == 0){
            cout << i << endl;
            return;
        }
    }
    cout << -1 << endl;
}

B - Base K

$ A, B $ を 10進数に直した積を出力
提出コード

void solve(){
    ll K;
    string A, B;
    cin >> K >> A >> B;
    reverse(A.begin(), A.end());
    reverse(B.begin(), B.end());
    ll a = 0, b = 0;
    {
        ll base = 1;
        REP(i,A.size()){
            a += base * (A[i] - '0');
            base *= K;
        }
    }
    {
        ll base = 1;
        REP(i,B.size()){
            b += base * (B[i] - '0');
            base *= K;
        }
    }
    cout << a * b << endl;
}

C - Long Sequence

$ sum = \sum A_i $ とすると、$ X $ より大きくならないギリギリの $ A $ の連結数は $ cnt = \lfloor \frac{X}{sum} \rfloor $ となる
そのため、すでに $ cnt $ 個 $ A $ が連結しているとして、残りを愚直に見ていく
提出コード

void solve(){
    int N;
    cin >> N;
    vector<ll> A(N);
    REP(i,N) cin >> A[i];
    ll sum = accumulate(A.begin(), A.end(), 0LL);
    ll X;
    cin >> X;
    ll res = X - X / sum * sum;
    ll cnt = X / sum * N;
    REP(i,N){
        if(res >= 0){
            res -= A[i];
            cnt++;
        }
    }
    cout << cnt << endl;
}

D - FG operation

$ dp[i][j] := i $ 番目まで操作を行ったときに、一番左端の値が $ j $ のときの場合の数としてDPをする
提出コード

void solve(){
    int N;
    cin >> N;
    vector<int> A(N);
    REP(i,N) cin >> A[i];
    vector dp(N, vector<mint>(10, 0));
    dp[1][(A[0]+A[1])%10] += 1;
    dp[1][(A[0]*A[1])%10] += 1;
    for(int i=2;i<N;i++){
        REP(j,10) if(dp[i-1][j] != 0){
            dp[i][(j + A[i])%10] += dp[i-1][j];
            dp[i][(j * A[i])%10] += dp[i-1][j];
        }
    }
    REP(i,10) cout << dp[N-1][i] << endl;
}

F - Distance Sums 2

全方位木DPみたいなやつ
最初に適当な頂点を根としたときの各頂点の子の数と根の答えを求める
その後、隣接頂点に移動しながら差分を計算する
隣接頂点の子の数を $ sz_{nv} $ とすると、根を $ nv $ としたときに $ sz_{nv} $ だけ今の根の答えから少なくなる
また、残りの $ N - sz_{nv} $ だけ今の根の答えから増えるので、今の根の答えを $ ans_v $ とすると $ ans_{nv} = ans_v - sz_{nv} + N - sz_{nv} = ans_v + N - 2sz_{nv} $ となる
提出コード

void solve(){
    int N;
    cin >> N;
    vector<vector<int>> G(N);
    vector<int> u(N-1), v(N-1);
    REP(i,N-1){
        cin >> u[i] >> v[i];
        G[--u[i]].emplace_back(--v[i]);
        G[v[i]].emplace_back(u[i]);
    }
    vector<ll> sz(N, 1);
    vector<ll> ans(N);
    auto dfs1 = [&](auto && self, int v, int par = -1) -> void{
        for(auto nv : G[v]){
            if(nv == par) continue;
            self(self, nv, v);
            sz[v] += sz[nv];
            ans[v] += ans[nv] + sz[nv];
        }
    };
    
    auto dfs2 = [&](auto && self, int v, int par = -1) -> void{
        for(auto nv : G[v]){
            if(nv == par) continue;
            ans[nv] = ans[v] - sz[nv] + N - sz[nv];
            self(self, nv, v);
        }
    };
    dfs1(dfs1, 0);
    dfs2(dfs2, 0);
    REP(i,N) cout << ans[i] << endl;
}