AtCoder Beginner Contest 248（ABC248）

atcoder.jp

Bondo416さんのユニークビジョンプログラミングコンテスト2022（AtCoder Beginner Contest 248）での成績：1018位
パフォーマンス：1469相当
レーティング：1436→1440 (+4) :)#AtCoder #ユニークビジョンプログラミングコンテスト2022（ABC248） https://t.co/ZWmhFA5jSA

— ボンド@競プロ (@bond_cmprog) April 16, 2022

A - Lacked Number

$ S $ に含まれない数字を全探索する

提出コード

void solve(){
    string S;
    cin >> S;
    for(char c='0';c<='9';c++){
        bool ok = true;
        for(char s : S) if(c == s) ok = false;
        if(ok){
            cout << c << endl;
            return;
        }
    }
}

B - Slimes

シミュレートをして回数を数える

提出コード

void solve(){
    ll A, B, K;
    cin >> A >> B >> K;
    int ans = 0;
    while(A < B){
        A *= K;
        ans++;
    }
    cout << ans << endl;
}

C - Dice Sum

$ dp[i][j][k] := i $ 番目まで見て、最後に選んだものが $ j $ のときに、その総和が $ k $ の場合の数としてDPをする

提出コード

void solve(){
    int N, M, K;
    cin >> N >> M >> K;
    vector dp(55, vector<mint>(2525));
    REP(i,1,M+1) dp[i][i] = 1;
    REP(_,N-1){
        vector nxt(55, vector<mint>(2525));
        REP(j,1,M+1){
            REP(k,1,M+1){
                REP(sum,K+1) if(sum+k <=K){
                    nxt[k][sum+k] += dp[j][sum];
                }
            }
        }
        swap(dp, nxt);
    }
    mint ans = 0;
    REP(i,1,M+1)REP(j,K+1) ans += dp[i][j];
    cout << ans << endl;
}

D - Range Count Query

$ A_i $ の要素ごとにそのインデックスをvectorなどに入れておくことで、二分探索で $ [L, R] $ の範囲にある個数を数えることができる

提出コード

void solve(){
    int N;
    cin >> N;
    vector<int> A(N);
    REP(i,N) cin >> A[i];
    int Q;
    cin >> Q;
    RangeCountExact<int> cnt(A);
    while(Q--){
        int l, r, x;
        cin >> l >> r >> x;
        --l;
        cout << cnt.get(l, r, x) << endl;
    }
}

E - K-colinear Line

$ K = 1 $ の場合のみ infinityなのでそれ以外の場合を考える
$ i $ 番目の頂点と $ j ( j ≠ i ) $ 番目の頂点の直線を求め、その直線をmapなどで数える
数えた直線の個数が $ K - 1 $ 以上ならその直線を答えに加える

提出コード

void solve(){
    int N, K;
    cin >> N >> K;
    vector<ll> x(N), y(N);
    REP(i,N) cin >> x[i] >> y[i];
    if(K == 1){
        cout << "Infinity" << endl;
        return;
    }
    set<tuple<ll, ll, ll>> st;
    REP(i,N){
        map<pair<ll, ll>, int> mp;
        REP(j,N) if(i != j) {
            ll x1 = x[j] - x[i], y1 = y[j] - y[i];
            ll g1 = gcd(abs(x1), abs(y1));
            x1 /= g1, y1 /= g1;
            if(x1 == 0) continue;
            if(y1 == 0) continue;
            if(x1 < 0) x1 *= -1, y1 *= -1;
            if(x1 == 0 and y1 == 0) continue;
            mp[{x1, y1}]++;
        }
        for(auto [k, v] : mp){
            auto [x1, y1] = k;
            if(v + 1>= K){
                if(x1 == 0 or y1 == 0) st.insert({x1, y1, 0});
                else st.insert({x1, y1, y[i] * x1 - y1 * x[i]});
            }
        }
    }

    map<int, int> mpx, mpy;
    REP(i,N){
        mpx[x[i]]++;
        mpy[y[i]]++;
    }
    int ans = (int)st.size();
    for(auto [k, v] : mpx) if(v >= K) ans++;
    for(auto [k, v] : mpy) if(v >= K) ans++;
    cout << ans << endl;
}