AtCoder Beginner Contest 164（ABC164） - 接着剤の精進日記

冷えた

うーん
Bondo416さんのAtCoder Beginner Contest 164での成績：3486位
パフォーマンス：938相当
レーティング：1418→1378 (-40) :(#AtCoder https://t.co/G76T1Eh3XE
— ボンド@競プロ (@bond_cmprog) 2020年4月26日

A - Sheep and Wolves

$S \leq W$ なら"unsafe" そうでないなら"safe"を出力すればいい
提出コード

void solve(){
    int S, W;
    cin >> S >> W;
    if(S <= W) cout << "unsafe" << endl;
    else cout << "safe" << endl;
}

B - Battle

制約が小さいので愚直にシミュレートしても間に合う
どちらかの体力が先に0になったほうが負け
提出コード

void solve(){
    int A, B, C, D;
    cin >> A >> B >> C >> D;
    int turn = 0;
    while(A > 0 && C > 0){
        if(turn % 2 == 0){
            C -= B;
        }
        else A -= D;
        turn = 1 - turn;
    }
    if(A <= 0) cout << "No" << endl;
    else cout << "Yes" << endl;
}

C - gacha

setに入れていってそのsizeを出力する
提出コード

void solve(){
    int N;
    cin >> N;
    set<string> s;
    REP(i,N){
        string S;
        cin >> S;
        s.insert(S);
    }
    cout << size(s) << endl;
}

D - Multiple of 2019

これ難しい
こういうのはZero-Sum Rangesっぽくやるのが大体正解になりそう
2019が合成数だから出来なくないか、と思っていたら実は10と互いに素だから出来る
完全に忘れてたんだけどABC158-Eこれとほぼ同じらしい
文字列を右から見ていって、mod 2019 の値を順次取っていき、最後に同じ値同士の組み合わせの総和が答え
提出コード

void solve(){
    string S;
    cin >> S;
    reverse(S.begin(), S.end());
    map<int, ll> mp;
    ll cur = 0;
    ll ans = 0;
    mp[0]++;
    ll fac = 1;
    REP(i,S.size()){
        cur = (cur + (S[i] - '0') * fac) % 2019;
        fac *= 10;
        fac %= 2019;
        cur %= 2019;
        mp[cur]++;
    }
 
    for(auto x : mp) ans += x.second * (x.second - 1) / 2;
    cout << ans << endl;
}

E - Two Currencies

グラフを拡張してダイクストラするあれ
各頂点ごとに、持っている銀貨の枚数ごとの最小時間を考える
この時、必要な銀貨の枚数は最大でも $A_{max}(N - 1)$ なので $NA_{max}$ 程度まで考えればいい
また、辺の本数も $M \leq 100$ なので拡張したグラフ上でダイクストラを行っても十分に間に合う
提出コード

void solve(){
    int N, M, S;
    cin >> N >> M >> S;
    vector<vector<tuple<int, int, int>>> G(N);
    vector<int> C(N), D(N);
    REP(i,M){
        int U, V, A, B;
        cin >> U >> V >> A >> B;
        --U, --V;
        G[U].emplace_back(V, A, B);
        G[V].emplace_back(U, A, B);
    }
    REP(i,N) cin >> C[i] >> D[i];
    vector<vector<ll>> dp(N, vector<ll>(2525, LINF));
    chmin(S, 2524);
    dp[0][S] = 0;
    priority_queue<tuple<ll, int, int>,vector<tuple<ll, int, int>>, greater<tuple<ll, int, int>>> pq; //cost, coins, cur;
    pq.emplace(0, S, 0);
    while(!pq.empty()){
        auto[cost, coins, cur] = pq.top(); pq.pop();
        
        // 今いる地点で銀貨にする
        if(chmin(dp[cur][min(2524, coins + C[cur])], cost + D[cur])){
            pq.emplace(dp[cur][min(2524, coins + C[cur])], min(2524, coins + C[cur]), cur);
        }

        for(auto [to, a, b] : G[cur]){
            if(coins < a) continue;
            if(chmin(dp[to][coins-a], cost + b)){
                pq.emplace(dp[to][coins-a], coins - a, to);
            }
        }
    }
    vector<ll> ans(N, LINF);
    for(int i=1;i<N;i++) REP(j,2525) chmin(ans[i], dp[i][j]);
    for(int i=1;i<N;i++) cout << ans[i] << endl;
}

おわりに

Dは解けないとだめなやつだったね
素数じゃないと出来なくない？って思い込んでしまった