AtCoder Beginner Contest 208（ABC208）

atcoder.jp

Bondo416さんのAtCoder Beginner Contest 208での成績：1802位
パフォーマンス：1155相当
レーティング：1439→1414 (-25) :(#AtCoder #ABC208 https://t.co/rNJgYFafvO

— ボンド@競プロ (@bond_cmprog) July 4, 2021

A - Rolling Dice

サイコロを $ A $ 回振ったときに出た目の合計として考えられる最小値以上、最大値以下ならばすべてあり得るので $ B $ がその範囲にあるかどうかを調べる
提出コード

void solve(){
    int A, B;
    cin >> A >> B;
    if(A <= B and B <= A * 6) cout << "Yes" << endl;
    else cout << "No" << endl;
}

B - Factorial Yen Coin

$ 10! $ の硬貨から順に払えるだけ払えばいい
提出コード

void solve(){
    ll P;
    cin >> P;
    ll cur = 1;
    ll ans = 0;
    for(int i=1;i<=10;i++) cur *= i;
    ll base = 10;
    while(P > 0){
        ans += P / cur;
        P %= cur;
        cur /= base;
        base--;
    }
    cout << ans << endl;
}

C - Fair Candy Distribution

$ N $ 人の人はそれぞれ $ \lfloor \frac{K}{N} \rfloor $ だけ必ず貰える
残りの $ K \pmod{N} $ は国民番号の小さい順に配れるだけ配ればいいので、国民番号順にソートをし実際に1個ずつ配ればいい
提出コード

void solve(){
    int N;
    ll K;
    cin >> N >> K;
    vector<ll> a(N);
    REP(i,N) cin >> a[i];
    vector<int> idx(N);
    iota(idx.begin(), idx.end(), 0);
    sort(idx.begin(), idx.end(), [&](int x, int y){
        return a[x] < a[y];
    });
    ll base = K / N;
    K %= N;
    vector<int> ans(N);
    REP(i,K) ans[idx[i]]++;
    REP(i,N){
        cout << base + ans[i] << endl;
    }
}

D - Shortest Path Queries 2

$ f(s, t, k) $ が求まっているとき、$ f(s, t, k+1) $ は $ k+1 $ の辺を使うかどうかで求めることが出来る
これは、ワーシャルフロイド法とほとんど同じもので求めることが出来る
各 $ (s, t) $ に対し $ f(s, t, k) $ の値を利用して最小値を求め、最後に $ f(s, t, k+1) $ の値を更新する
提出コード

void solve(){
    int N, M;
    cin >> N >> M;
    vector dist(N, vector(N, INF));
    REP(i,N) dist[i][i] = 0;
    REP(i,M){
        int a, b, c;
        cin >> a >> b >> c;
        --a, --b;
        dist[a][b] = c;
    }
    ll ans = 0;
    REP(k,N){
        auto nxt = vector<vector<int>>(N, vector<int>(N, INF));
        REP(s,N) REP(t,N){
            nxt[s][t] = min(dist[s][t], dist[s][k] + dist[k][t]);
            if(nxt[s][t] < INF) ans += nxt[s][t];
        }
        swap(dist, nxt);
    }
    cout << ans << endl;
}