AtCoder Beginner Contest 280（ABC280）

atcoder.jp

Bondo416さんのデンソークリエイトプログラミングコンテスト2022 Winter(AtCoder Beginner Contest 280)での成績：1524位
パフォーマンス：1239相当
レーティング：1570→1541 (-29) :(#AtCoder #デンソークリエイトプログラミングコンテスト2022Winter(ABC280) https://t.co/Jve4EBGnYG

— ボンド@競プロ (@bond_cmprog) December 3, 2022

A - Pawn on a Grid

ループで # の個数を数える

提出コード

void solve() {
    int H, W;
    cin >> H >> W;
    vector<string> S(H);
    REP(i, H) cin >> S[i];
    int res = 0;
    REP(i, H) REP(j, W) res += (S[i][j] == '#');
    cout << res << endl;
}

B - Inverse Prefix Sum

累積和を $ sum $ として、$ S_i - sum $ を答えに入れ、この値を $ sum $ に加算する

提出コード

void solve() {
    int N;
    cin >> N;
    vector<ll> S(N);
    REP(i, N) cin >> S[i];
    vector<ll> ans;
    ll sum = 0;
    REP(i, N) {
        ans.emplace_back(S[i] - sum);
        sum += ans.back();
    }
    for (auto x : ans)
        cout << x << " ";
    cout << endl;
}

C - Extra Character

$ S_i \neq T_i $ となる $ i $ を出力する

提出コード

void solve() {
    string S, T;
    cin >> S >> T;

    int ans = T.size();
    REP(i, S.size()) if (S[i] != T[i]) {
        ans = i + 1;
        break;
    }
    cout << ans << endl;
}

D - Factorial and Multiple

$ K $ を素因数分解し、各素因数 $ p_i $ ごとに $ N_i ! $ が $ p_i ^{a_i} $ の倍数となる最小の $ N_i $ を求める
求めた $ N_i $ のうち最大のものが答えとなる

提出コード

void solve() {
    ll K;
    cin >> K;
    auto res = prime_factorize(K);
    ll ma = 1;
    for (auto [num, cnt] : res) {
        for (ll i = num; i <= K; i += num) {
            ll res = i;
            while (res % num == 0) {
                res /= num;
                cnt--;
            }
            if (cnt <= 0) {
                chmax(ma, i);
                break;
            }
        }
    }
    cout << ma << endl;
}

E - Critical Hit

$ dp[i] := $ モンスターの体力を $ i $ だけ減らしたときの攻撃回数の期待値としてDPを行う

提出コード

void solve() {
    int N, P;
    cin >> N >> P;
    vector dp(N + 2, mint(0));
    mint a = mint(P) / 100;
    mint b = mint(1) - a;
    dp[0] = 0;
    REP(i, 1, N + 1) { dp[i] = (dp[max(0, i - 2)] + 1) * a + (dp[i - 1] + 1) * b; }
    cout << dp[N] << endl;
}

F - Pay or Receive

ポテンシャル付きUnionFindを使って判定をおこなう
$ X, Y $ が同じ連結成分ではないときには nan
$ X, Y $ が非零の閉路に含まれるときは inf
そうでないときはポテンシャルの差分を出力すれば良い

提出コード

void solve() {
    int N, M, Q;
    cin >> N >> M >> Q;
    PotentializedUnionFind<ll> uf(N);
    REP(_, M) {
        int A, B, C;
        cin >> A >> B >> C;
        uf.unite(--A, --B, C);
    }
    while (Q--) {
        int X, Y;
        cin >> X >> Y;
        --X, --Y;
        if (!uf.issame(X, Y)) cout << "nan" << endl;
        else if (!uf.dist(X, Y)) cout << "inf" << endl;
        else cout << uf.dist(X, Y).value() << endl;
    }
}