接着剤の精進日記

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

トップ > AtCoderBeginnerContest > キャディプログラミングコンテスト2021(AtCoder Beginner Contest 193)

キャディプログラミングコンテスト2021(AtCoder Beginner Contest 193)

AtCoderBeginnerContest AtCoderBeginnerContest193 ABC ABC193

atcoder.jp

A - Discount

$ 100 \times (1 - \frac{B}{A}) $ を出力する
提出コード

void solve(){
    double A, B;
    cin >> A >> B;
    printf("%.12lf\n", (1 - B / A) * 100);
}

B - Play Snuke

$ A_i \geq X_i $ のときは売り切れて買えない
それ以外の場合で、最小となる $ P_i $ を探す
提出コード

void solve(){
    int N;
    cin >> N;
    vector<ll> A(N), P(N), X(N);
    REP(i,N) cin >> A[i] >> P[i] >> X[i];
    ll ans = LINF;
    REP(i,N){
        if(A[i] >= X[i]) continue;
        chmin(ans, P[i]);
    }
    if(ans == LINF) ans = -1;
    cout << ans << endl;
}

C - Kaprekar Number

全探索をする
$ i \leq \sqrt{N} $ を満たす $ i $ について $ i^j \leq N ( j \geq 2 ) $ を満たすものをsetなどで管理すればいい
提出コード

void solve(){
    ll N;
    cin >> N;
    ll ans = N;
    set<ll> st;
    for(ll i=2;i*i<=N;i++){
        ll cur = i * i;
        while(cur <= N){
            st.insert(cur);
            cur *= i;
        }
    }
    cout << N - (ll)st.size() << endl;
}

D - Poker

二人の手札の場合の数は $ all = (9K - 8) (9K-9) $ となるので高橋くんが勝つときの場合の数を $ sum $ とすると $ \frac{sum}{all} $ が答え
$ sum $ については、高橋くんと青木くんの残りのカードについて全探索をして求めればいい
提出コード

void solve(){
    ll K;
    string S, T;
    cin >> K >> S >> T;
    vector<int> cntS(10), cntT(10);
    REP(i,4){
        cntS[S[i]-'0']++;
        cntT[T[i]-'0']++;
    }
    double sum = 0.0;
    double all = (9 * K - 8) * (9 * K - 9);
    for(int i=1;i<=9;i++){
        for(int j=1;j<=9;j++){
            if(i == j){
                if(cntS[i] + cntT[j] + 2 > K) continue;
            }
            else{
                if(cntS[i] + cntT[i] + 1 > K) continue;
                if(cntS[j] + cntT[j] + 1 > K) continue;
            }
            ll sumS = 0, sumT = 0;
            cntS[i]++;
            cntT[j]++;
            for(ll k=1;k<=9;k++){
                sumS += k * pow(10, cntS[k]);
                sumT += k * pow(10, cntT[k]);
            }
            cntS[i]--;
            cntT[j]--;
            if(sumS > sumT){
                if(i == j){
                    sum += (K - cntS[i] - cntT[i]) * (K - cntS[i] - cntT[i] - 1);
                }
                else sum += (K - cntS[i] - cntT[i]) * (K - cntS[j] - cntT[j]);
            }
        }
    }
    printf("%.12lf\n", sum / all);
}

E - Oversleeping

条件より $ (P + Q)a + P + q = (2X + 2Y)b + X + y (0 \leq q \lt Q, 0 \leq y \lt Y) $ を満たす $ a, b $ を見つけたい
左辺は $ P + Q $ の周期、右辺は $ 2X + 2Y $ の周期になっているので
\begin{align} t& \mod (P + Q) = P+q \\ t& \mod (2X + 2Y) = X+y \end{align}

を満たす最小の非負整数 $ t $ を求めることができればいい
これはACLのcrtを使えば求めることができる
提出コード

void solve(){
    ll X, Y, P, Q;
    cin >> X >> Y >> P >> Q;
    ll ans = 9 * LINF;
    for(int q = 0; q < Q; q++){
        for(int y = 0; y < Y; y++){
           auto [a, b] = crt({P+q, X+y}, {P+Q, 2*X+2*Y});
           if(a == 0 and b== 0) continue;
           chmin(ans, a);
        }
    }
    if(ans == 9 * LINF) cout << "infinity" << endl;
    else cout << ans << endl;
}