接着剤の精進日記

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

AtCoder Beginner Contest 167（ABC167）

AtCoderBeginnerContest167 AtCoderBeginnerContest ABC167 ABC

atcoder.jp

数を数えられない

A - Registration

substrで比較すればいい
Tをpop_back()するの頭いいね
提出コード

void solve(){
    string S, T;
    cin >> S >> T;
    int n = S.size();
    if(S == T.substr(0,n)){
        cout << "Yes" << endl;
    }
    else cout << "No" << endl;
}

B - Easy Linear Programming

1, 0, -1の順に取れるだけ取っていけばいい

提出コード

void solve(){
    ll A, B, C, K;
    cin >> A >> B >> C >> K;
    ll sum = 0;
    if(A >= K){
        sum += K;
        K = 0;
    }
    else{
        sum += A;
        K -= A;
    }
    if(B >= K){
        K = 0;
    }
    else K -= B;
    sum -= K;
    cout << sum << endl;
}

C - Skill Up

流石にもう解ける人のほうが多いね
bit全探索をする
提出コード

void solve(){
    int N, M, X;
    cin >> N >> M >> X;
    vector<ll> C(N);
    vector<vector<ll>> A(N, vector<ll>(M));
    REP(i,N){
        cin >> C[i];
        REP(j,M){
            cin >> A[i][j];
        }
    }
    ll sum = LINF;
    REP(i,1<<N){
        ll tmp = 0;
        vector<ll> t(N);
        REP(j,N){
            if(i >> j & 1){
                tmp += C[j];
                REP(k,M) t[k] += A[j][k];
            }
        }
        bool ok = true;
        REP(k,M) if(t[k] < X) ok = false;
        if(ok) chmin(sum, tmp);
    }
    if(sum == LINF) sum = -1;
    cout << sum << endl;
}

D - Teleporter

脳死ダブリングをした
周期で見る解法もあるけどダブリング出来るならダブリングのほうがバグらせない気がする
コンテスト中全人類ダブリングできるのかーとなっていた
提出コード

void solve(){
    ll N, K;
    cin >> N >> K;
    vector<int> A(N);
    REP(i,N){
        cin >> A[i];
        --A[i];
    }
    vector<vector<ll>> to(62, vector<ll>(N));
    REP(i,N) to[0][i] = A[i];
    REP(i,60) REP(j,N) to[i+1][j] = to[i][to[i][j]];
    int cur = 0;
    REP(j,60){
        if((K >> j) & 1){
            cur = to[j][cur];
        }
    }
    cout << cur + 1 << endl;
}

E - Colorful Blocks

全人類数え上げがうますぎる
まず隣り合う組を固定することを考える
K = 0のときはM \times (M - 1)^{N-1}通り
K = iのときは、 M \times (M - 1)^{N-1-i}通りあり、隣り合う組の選び方が _{N - 1} C _ i通りとなるのでその積の総和を求めればいい
提出コード

using mint = Fp<MOD>;
BiCoef<mint> bc(202020);

void solve(){
    int N, M, K;
    cin >> N >> M >> K;
    
    mint ans = 0;
    for(int i=0;i<=K;i++){
        ans += mint(M) * modpow(mint(M-1), N-1-i) * bc.com(N-1, i);
    }
    cout << ans << endl;
}

F - Bracket Sequencing

括弧列のときはまず'('を+1、')'を-1としたときに、その総和が0になっている必要がある
また、括弧列を並べたときに、途中で負の値になっている場合は括弧列にはならない
解説放送の考え方がわかりやすかったのでその方針で考える
各文字列に対して、折れ線グラフで考えたときに一番底の部分（最小の値）と最終的な総和のペアを考える
総和が正の時、最小が大きい順かつ、総和が大きい順に取っていけばいい
総和が負になったときが問題になるが、総和が正のものを、折れ線グラフを左から見ている状態とする
そうすると、総和が負のときは折れ線グラフを逆から見たものとすると、総和が正のときと同じ状態とみなせる
そのため、それぞれに対し、今の総和に最小の値を足したときに負になれば"No"となり、そのようにならないときは必ず"Yes"になる
提出コード

void solve(){
    int N;
    cin >> N;
    vector<string> S(N);
    REP(i,N) cin >> S[i];
    vector<pair<int, int>> posi, nega;

    int sum = 0;
    REP(i,N){
        int cnt = 0;
        int mi = 0;
        REP(j,S[i].size()){
            if(S[i][j] == '(') cnt++;
            else cnt--;
            chmin(mi, cnt);
        }
        if(cnt > 0) posi.emplace_back(mi, cnt);
        else nega.emplace_back(mi - cnt, -cnt);
        sum += cnt;
    }
    if(sum != 0){
        cout << "No" << endl;
        return;
    }
    sort(posi.rbegin(), posi.rend());
    sort(nega.rbegin(), nega.rend());
    int cur = 0;
    for(auto [mi, cnt] : posi){
        // cout << mi << " " << cnt << endl;
        if(cur + mi < 0){
            cout << "No" << endl;
            return;
        }
        cur += cnt;
    }
    cur = 0;
    for(auto [mi, cnt] : nega){
        // cout << mi << " " << cnt << endl;
        if(cur + mi < 0){
            cout << "No" << endl;
            return;
        }
        cur += cnt;
    }
    cout << "Yes" << endl;
}

おわりに

数を数えられる人間になりたいね

Codeforces Round #640 (Div. 4)

Codeforces Codeforces Round #640 (Div. 4)

codeforces.com

緑以下Ratedのdiv4
全完出来たけど前半割と難しくない？後半はdiv3より流石に簡単だったけど（というかdiv3の後ろ難しすぎる）

A. Sum of Round Numbers

問題文

正の整数nが与えられる
nを先頭桁以外が0の整数の和で表現する
そのような整数の最小の数とそのそれぞれの整数を出力せよ

解法

下の桁から見ていき、その桁が0以外なら桁数分掛けたものを答えに加える
提出コード

void solve(){
    int n;
    cin >> n;
    vector<int> ans;
    int cur = 1;
    while(n > 0){
        int d = n % 10;
        if(d > 0) ans.emplace_back(d * cur);
        cur *= 10;
        n /= 10;
    }
    cout << ans.size() << endl;
    for(auto x : ans) cout << x << " ";
    cout << endl;
}

B. Same Parity Summands

問題文

正の整数nとkが与えられる
k個の0以上の整数からなる数列aの和がnとなるようなものを見つけたい
ただし、数列の要素の偶奇は全て一致していなければならない
このような数列が存在する時、その一つを出力せよ

解法

頭壊れた
nが奇数、kが偶数のときは絶対作れない
nが奇数、kが奇数のときはn \geq kなら必ず作れる
nが偶数、kが偶数のときはn \geq 2kなら必ず作れる
nが偶数、kが奇数のときはn \geq kなら必ず作れる
作れるときは一番小さい要素を出力して、最後の一つで帳尻を合わせればいい
提出コード

void solve(){
    int n, k;
    cin >> n >> k;
    if(n == k){
        cout << "YES" << endl;
        REP(i,k) cout << 1 << " ";
        cout << endl;
        return;
    }
    if(n < k){
        cout << "NO" << endl;
        return;
    }

    if(n & 1){
        if(k & 1){
            if(n >= k){
                cout << "YES" << endl;
                REP(i,k-1) cout << 1 << " ";
                cout << n - (k - 1) << endl;
            }
            else cout << "NO" << endl;
        }
        else cout << "NO" << endl;
    }
    else{
        if(k & 1){
            if(n >= 2 * k){
                cout << "YES" << endl;
                REP(i,k-1) cout << 2 << " ";
                cout << n - 2 * (k - 1) << endl;
            }
            else cout << "NO" << endl;
        }
        else{
            if(n >= k){
                cout << "YES" << endl;
                REP(i,k-1) cout << 1 << " ";
                cout << n - (k - 1) << endl;
            }
            else cout << "NO" << endl;
        }
    }
}

C. K-th Not Divisible by n

問題文

正の整数nとkが与えられる
nの倍数でないもののうち、k番目の整数を出力せよ

解法

にぶたんでもできそうだけど算数したほうが早そうなので算数をした
まず、 \lfloor \frac{k}{n - 1} \rfloor番目のnの倍数以下の整数は全て使うことになる
この時、nの倍数でないものの個数は \lfloor \frac{k}{n - 1} \rfloor \times (n - 1)個となる
そのため、残っている個数は(n -1)個以下なので、 \lfloor \frac{k}{n - 1} \rfloor \times nからその分を足していく
ただし、残りが0個のときはその分引いて上げる必要がある
提出コード

void solve(){
    ll n, k;
    cin >> n >> k;
    ll cur = k / (n - 1) * n;
    k -= k / (n - 1) * (n - 1);
    REP(i,k) cur++;
    if(k % (n-1) == 0) cur--;
    cout << cur << endl;
}

D. Alice, Bob and Candies

問題文

n個のキャンディがありそのサイズはa_iである
Aliceはこのキャンディーを左から、Bobは右から食べていく
この時、1ターンで食べるキャンディのサイズの合計は、その前のターンより心に大きくなるまで食べなければならず、大きくなった瞬間食べるのをやめる
Aliceから最初のターンを始める時、終わるまでにかかるターン数、Aliceが食べたキャンディのサイズの合計、Bobが食べたキャンディのサイズの合計を出力せよ

解法

実際にシミュレートしていけばいい

提出コード

void solve(){
    int n;
    cin >> n;
    vector<int> a(n);
    REP(i,n) cin >> a[i];
    int cur = 0;
    int l = 0, r = n - 1;
    int turn = 0;
    int Alice = 0, Bob = 0;
    while(l <= r){
        int tmp = 0;
        if(turn & 1){
            while(tmp <= cur && l <= r){
                tmp += a[r];
                r--;
            }
            Bob += tmp;
        }
        else{
            while(tmp <= cur && l <= r){
                tmp += a[l];
                l++;
            }
            Alice += tmp;
        }
        cur = tmp;
        turn++;
    }
    cout << turn << " " << Alice << " " << Bob << endl;
}

E. Special Elements

問題文

n個の正の整数からなる数列aが与えられる
a_i = a_l + a_{l+1} + ... + a_r ( 1 \leq l \lt r \leq n)を満たすペア(l, r)が存在する時、a_iをspecialと呼ぶ
与えられた数列aのうち、specialなものの個数を出力せよ

解法

全探索しても十分に間に合うので区間の和を全探索する
メモリの制約が小さいのでしゃくとりっぽくやった
提出コード

void solve(){
    int n;
    cin >> n;
    vector<int> a(n);
    map<int, int> mp;
    REP(i,n){
        cin >> a[i];
        mp[a[i]]++;
    }
    int ans = 0;
    for(int i=2;i<n;i++){
        int sum = 0;
        REP(j,i) sum += a[j];
        if(mp.count(sum)){
            ans += mp[sum];
            mp.erase(sum);
        }
        for(int j=i;j<n;j++){
            sum -= a[j-i];
            sum += a[j];
            if(mp.count(sum)){
                ans += mp[sum];
                mp.erase(sum);
            }
        }
    }
    cout << ans << endl;
}

F. Binary String Reconstruction

問題文

'0'と'1'からなる"binary string" sがある
sのうち、長さが2の連続部分文字列を考える
この連続部分文字列のうち、'1'が出現する個数が0、1、2個のものの個数をそれぞれn0、n1、n2とする
n0、n1、n2が与えられるのでこれを満たすような文字列 sを出力せよ
これを満たす文字列は必ず存在することが保証される

解法

初めにn0の分だけ"00...0"を作る
今作ったものに"1010..."のように作ったものをくっつける
この時偶数分だけ後ろにつけて、奇数分があれば先頭に1個くっつけると楽
後は先頭か後ろが'1'になっているのでn2分だけ"111..."をくっつける 提出コード

void solve(){
    int n0, n1, n2;
    cin >> n0 >> n1 >> n2;
    string ans = "";
    if(n0 > 0) ans = string(n0+1, '0');
    if(n1 > 0){
        if(ans == "") ans = '0';
        if(n1 % 2 == 0){
            REP(i,n1-1){
                if(i & 1) ans += '0';
                else ans += '1';
            }
            ans = "1" + ans;
        }
        else{
            REP(i,n1){
                if(i & 1) ans += '0';
                else ans += '1';
            }
        }
    }
    if(ans == "") ans = string(n2+1, '1');
    else if(ans[0] == '1') ans = string(n2, '1') + ans;
    else if(ans.back() == '1') ans += string(n2, '1');
    cout << ans << endl;
}

G. Special Permutation

問題文

正の整数nが与えられる
1 からnまでの順列pを考える
この時、1 \leq i \lt nに対して、 2 \leq |p_i - p_{i+1} | \leq 4を満たすような順列pを求めたい
このような順列が存在する時、そのような順列を一つ出力せよ

解法

実は、 n \geq 4のとき ... 7, 5, 3, 1, 4, 2, 4, 6, 8, ... のように[3, 1, 4, 2]の左側に奇数、右側に偶数を並べていくことでそのような順列を作ることが出来る
残り時間が少なかったのもあってコンテスト中は全探索通りそうだなーって思ったので全探索を書いて投げた
間に合いそうだなーって思ったけどちゃんと見積もれてたわけじゃないので、こどふぉだとあんまりやらないほうがいいね
提出コード

void solve(){
    int n;
    cin >> n;
    if(n <= 2){
        cout << -1 << endl;
        return;
    }
    vector<vector<int>> G(n+10);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(i == j) continue;
            if(2 <= abs(i - j) &&  abs(i - j) <= 4) G[i].emplace_back(j);
        }
    }
    vector<int> ans;
    vector<bool> used(n + 10);
    auto dfs = [&](auto && self, int cur, int par, int cnt) -> bool{
        used[cur] = true;
        if(cnt == n){
            ans.push_back(cur);
            return true;
        }
        for(auto nv : G[cur]){
            if(nv == par) continue;
            if(used[nv]) continue;
            if(self(self, nv, cur, cnt + 1)){
                ans.push_back(cur);
                return true;
            }
        }
        used[cur] = false;
        return false;
    };

    dfs(dfs, 2, -1, 1);
    if(ans.size() < n){
        cout << -1 << endl;
        return;
    }
    for(auto x : ans) cout << x << " ";
    cout << endl;
}

おわりに

div4楽しい
序盤結構辛く感じたけどrated帯の人どうなんだろうね

AtCoder Beginner Contest 166（ABC166）

AtCoderBeginnerContest166 AtCoderBeginnerContest ABC166 ABC

atcoder.jp

水色で3完の人がいるらしいですよ、誰でしょうね

A - A?C

言われてるとおりにやる
提出コード

void solve(){
    string S;
    cin >> S;
    if(S == "ABC") cout << "ARC" << endl;
    else cout << "ABC" << endl;
}

B - Trick or Treat

ぱっと見で問題がよくわからなかった
お菓子をもらっている人をカウントすればいい
提出コード

void solve(){
    int N, K;
    cin >> N >> K;
    vector<int> cnt(N);
    REP(i,K){
        int d;
        cin >> d;
        REP(j,d){
            int a;
            cin >> a;
            --a;
            cnt[a]++;
        }
    }
    int ans = 0;
    REP(i,N) if(cnt[i] == 0) ans++;
    cout << ans << endl;
}

C - Peaks

一本の道を通っての部分読み飛ばしててUnionFind貼ってサンプル合わなくて気づいた
各頂点の隣接リストを見れば良いね

提出コード

void solve(){
    int N, M;
    cin >> N >> M;
    vector<int> H(N);
    REP(i,N) cin >> H[i];
    vector<vector<int>> G(N);
    REP(i,M){
        int a, b;
        cin >> a >> b;
        --a, --b;
        G[a].emplace_back(b);
        G[b].emplace_back(a);
    }
    int ans = 0;
    REP(i,N){
        int ma = H[i];
        bool ok = true;
        for(auto nv : G[i]){
            if(H[nv] >= ma){
                ok = false;
                break;
            }
        }
        if(ok) ans++;
    }
    cout << ans << endl;
}

D - I hate Factorization

これ難しいんですけど
1000くらいまで全探索すれば良さそうなのはぱっとわかって
そこから何故かBをO(1)で求めようとして沼った
微分を使うと4乗オーダーで見積もりが出来るらしいですよ（考えもしなかった）
Bも全探索すればいいですね、はい…
提出コード

void solve(){
    ll X;
    cin >> X;
    for(ll i=1;i<=2e3;i++){
        for(ll j=-2e3;j<=2e3;j++){
            if(i*i*i*i*i - j*j*j*j*j == X){
                cout << i << " " << j << endl;
                return;
            }
        }
    }
}

E - This Message Will Self-Destruct in 5s

これ緑difficultyまじ？壊れる
条件を考えるとi + A_i = j - A_jになるものを探せばいい
そのため左辺のものと右辺のものをmapなどで管理しておけば
後は先頭から見ていくいつものやつ
D解けなくて焦ってたのもあるけどこれ解けないのはだめだねーINF回見てるやつ
提出コード

void solve(){
    int N;
    cin >> N;
    map<ll, ll> L, R;
    ll ans = 0;
    REP(i,N){
        ll A;
        cin >> A;
        ans += L[i-A];
        ans += R[i+A];
        L[i+A]++;
        R[i-A]++;
    }
    cout << ans << endl;
}

F - Three Variables Game

まだ解いてないんだけどぱっと見後ろから貪欲とかそういう系に見える
大体の場合でYESにできそうだから、出来ないときの場合分けを考えるやつっぽい
全探索でも出来るらしい
うまくいくやつは雑にやってもNまで探索すればいいので間に合う
だめなときが問題になるけど、ダメな奴は基本的には早い段階で枝刈りされるので大丈夫なるパターン
なのでNに近い段階で駄目なパターンが多く見つかるというケースは少なくなりそう
だめになる時というのが、A+B+Cの値が小さい時になるけどA+B+Cが小さいときは最適に選ばないといけないことが増えて、状態数が小さくなり、その状態で駄目になるというのは早い段階で枝刈りされるという感じなのかな
提出コード

void solve(){
    int N, A, B, C;
    cin >> N >> A >> B >> C;
    vector<string> vs(N);
    REP(i,N) cin >> vs[i];
    string ans;
    auto dfs = [&](auto && self, int cur, int a, int b, int c) -> bool{
        if(cur == N) return true;

        if(vs[cur] == "AB"){
            if(a == 0 && b == 0) return false;
            if(0 < a && self(self, cur+1, a-1, b+1, c)){
                ans.push_back('B');
                return true;
            }
            if(0 < b && self(self, cur+1, a+1, b-1, c)){
                ans.push_back('A');
                return true;
            }
            return false;
        }

        if(vs[cur] == "AC"){
            if(a == 0 && c == 0) return false;
            if(0 < a && self(self, cur+1, a-1, b, c+1)){
                ans.push_back('C');
                return true;
            }
            if(0 < c && self(self, cur+1, a+1, b, c-1)){
                ans.push_back('A');
                return true;
            }
            return false;
        }

        if(vs[cur] == "BC"){
            if(b == 0 && c == 0) return false;
            if(0 < b && self(self, cur+1, a, b-1, c+1)){
                ans.push_back('C');
                return true;
            }
            if(0 < c && self(self, cur+1, a, b+1, c-1)){
                ans.push_back('B');
                return true;
            }
            return false;
        }
        return false;
    };

    dfs(dfs, 0, A, B, C);
    reverse(ans.begin(), ans.end());
    if(ans.size() < N) cout << "No" << endl;
    else{
        cout << "Yes" << endl;
        for(auto x : ans) cout << x << endl;
    }
}

おわりに

ここ3, 4回くらいの問題ほんと解けない
Dに数学置かれると辛くなりがち

AtCoder Beginner Contest 165（ABC165）

AtCoderBeginnerContest165 AtCoderBeginnerContest ABC165 ABC

atcoder.jp

ちょい伸び

A - We Love Golf

A \leq i \leq Bを全探索すればいい
提出コード

void solve(){
    int K, A, B;
    cin >> K >> A >> B;
    for(int i=A;i<=B;i++){
        if(i % K == 0){
            cout << "OK" << endl;
            return;
        }
    }
    cout << "NG" << endl;
}

B - 1%

愚直にシミュレートする
サンプルに最大ケースあるの優しいね
後はオーバーフローに注意？
提出コード

void solve(){
    ll X;
    cin >> X;
    ll cur = 100;
    int ans = 0;
    while(cur < X){
        cur += cur / 100;
        ans++;
    }
    cout << ans << endl;
}

C - Many Requirements

読解が難しかった
1 \leq A_1 \leq A_2 \leq ... \leq ... \leq A_N \leq Mを満たす場合の数は
重複組合せを考えると _{N + M - 1} C _Nで最大ケースでも十分に間に合う
そのため、dfsなどで全探索をすればいい
コンテスト中はこれを思い出してた
atcoder.jp

提出コード

void solve(){
    int N, M, Q;
    cin >> N >> M >> Q;
    vector<int> a(Q), b(Q), c(Q), d(Q);
    REP(i,Q){
        cin >> a[i] >> b[i] >> c[i] >> d[i];
        --a[i],--b[i];
    }
    ll ans = 0;
    auto dfs = [&](auto && dfs, vector<int> v) -> void{
        if(v.size() == N){
            ll tmp = 0;
            REP(i,Q){
                if(v[b[i]] - v[a[i]] == c[i]){
                    tmp += d[i];
                }
            }
            chmax(ans, tmp);
        }
        else{
            if(v.empty()){
                for(int i=1;i<=M;i++){
                    auto tmp = v;
                    tmp.push_back(i);
                    dfs(dfs, tmp);
                }
            }
            else{
                for(int i=v.back();i<=M;i++){
                    auto tmp = v;
                    tmp.push_back(i);
                    dfs(dfs, tmp);
                }
            }
        }
    };
    vector<int> v;
    dfs(dfs, v);
    cout << ans << endl;
}

D - Floor Function

これ難しい
手元で実験してみると、周期性があって、B-1のときに最大になっていることがわかる
なので、 min(B - 1, N)のときの答えを出力する
提出コード

void solve(){
    ll A, B, N;
    cin >> A >> B >> N;
    ll mi = min(B-1, N);
    cout << (A * mi) / B << endl;
}

E - Rotation Matching

こういうパズルっぽいの解けるようになる気がしないなあ
端同士の点と、真ん中の2点を取る
端 -> 真ん中 -> 端 -> ...の順に交互に取っていき、端は真ん中に、真ん中は端に寄せていく
2点(i, j)の差分の mod Nが重複しないようにするってことを考えるのが良いのかな
提出コード

void solve(){
    int N, M;
    cin >> N >> M;
    int a = 1, b = N - 1, c = N / 2, d = N / 2 + 1;
    REP(i,M){
        if(i & 1) cout << a++ << " " << b-- << endl;
        else cout << c-- << " " << d++ << endl;
    }
}

F - LIS on Tree

言われてみるとそれはそうなんだけど通す人々が多くて強いなーってなった
まず、パスで考えると普通のLISを解けばいい
木上で考えると、ある葉までのパス上の頂点はLISを更新していけばいい
後は、帰りがけのときにDPの更新を戻してあげればいい
これは行きがけのときにDPの値をメモっておいて、帰りがけのときにロールバックをしてあげると、\mathcal{O}(NlogN)で解くことが出来る
提出コード

void solve(){
    int N;
    cin >> N;
    vector<int> a(N);
    REP(i,N) cin >> a[i];
    vector<vector<int>> G(N);
    REP(i,N-1){
        int u, v;
        cin >> u >> v;
        --u, --v;
        G[u].emplace_back(v);
        G[v].emplace_back(u);
    }
    vector<int> ans(N, INF);
    vector<int> dp(N+1, INF);
    dp[0] = -INF;

    auto dfs = [&](auto && self, int cur, int par) -> void{
        int idx = lower_bound(dp.begin(), dp.end(), a[cur]) - dp.begin();
        int tmp = dp[idx];
        dp[idx] = a[cur];
        ans[cur] = lower_bound(dp.begin(), dp.end(), INF) - dp.begin() - 1;
        for(auto nv : G[cur]){
            if(nv == par) continue;
            self(self, nv, cur);
        }
        dp[idx] = tmp;
    };

    dfs(dfs, 0, -1);
    for(auto x : ans) cout << x << endl;
}

おわりに

青difficulty解けないなあ精進しないと

AtCoder Beginner Contest 164（ABC164）

AtCoderBeginnerContest164 AtCoderBeginnerContest ABC164 ABC

atcoder.jp

冷えた

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は解けないとだめなやつだったね
素数じゃないと出来なくない？って思い込んでしまった