AtCoder Beginner Contest 249（ABC249）

atcoder.jp

Bondo416さんのモノグサプログラミングコンテスト2022（AtCoder Beginner Contest 249）での成績：1645位
パフォーマンス：1159相当
レーティング：1440→1414 (-26) :(#AtCoder #モノグサプログラミングコンテスト2022（ABC249） https://t.co/ixl200nAom

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

A - Jogging

for文でそれぞれの移動距離を求める

提出コード

void solve(){
    int A, B, C, D, E, F, X;
    cin >> A >> B >> C >> D >> E >> F >> X;
    int t = 0, a = 0;
    for(int i=0;i<=X;){
        if(i + A <= X) t += A * B;
        else{
            t += (X - i) * B;
            break;
        }
        i += A + C;
    }
    for(int i=0;i<=X;){
        if(i + D <= X) a += D * E;
        else{
            a += (X - i) * E;
            break;
        }
        i += D + F;
    }
    if(t == a) cout << "Draw" << endl;
    else if(t > a) cout << "Takahashi" << endl;
    else cout << "Aoki" << endl;
}

B - Perfect String

大文字・小文字の判定と、setですべての文字が異なるかどうかを判定

提出コード

void solve(){
    string S;
    cin >> S;
    set<char> st;
    bool big = false;
    bool small = false;
    for(char c : S){
        st.insert(c);
        if('a' <= c and c <= 'z') small = true;
        if('A' <= c and c <= 'Z') big = true;
    }
    cout << (big and small and st.size() == S.size() ? "Yes" : "No") << endl;
}

C - Just K

bit全探索をする

提出コード

void solve(){
    int N, K;
    cin >> N >> K;
    vector<string> S(N);
    REP(i,N) cin >> S[i];
    int ans = 0;
    REP(i,1<<N){
        vector<int> cnt(26);
        REP(j,N) if(i >> j & 1){
            vector<int> _cnt(26);
            for(char c : S[j]) _cnt[c-'a']++;
            REP(k,26) if(_cnt[k]) cnt[k]++;
        }
        int tmp = 0;
        REP(j,26) if(cnt[j] == K) tmp++;
        chmax(ans, tmp);
    }
    cout << ans << endl;
}

D - Index Trio

予め、それぞれの要素ごとに個数をカウントしておく
$ A_j $ を固定すると、$ A_i $ は $ A_j $ の倍数となり、$ A_k $ は一つに定まるので、$ A_i $ を固定したときに $ A_j $ を調和級数で数えれば全体として $ O(N \log N) $ で求めることができる

提出コード

void solve(){
    int N;
    cin >> N;
    vector<int> A(N);
    REP(i,N) cin >> A[i];
    vector<ll> cnt(202020);
    REP(i,N) cnt[A[i]]++;
    ll ans = 0;
    REP(i,202020) if(cnt[i]){
        for(int j=i;j<202020;j+=i){
            int k = j / i;
            ans += cnt[i] * cnt[j] * cnt[k];
        }
    }
    cout << ans << endl;
}