接着剤の精進日記

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

トップ > AtCoder > エイシング プログラミング コンテスト 2020

エイシング プログラミング コンテスト 2020

AtCoder ABC 企業コン aising2020

atcoder.jp

A - Number of Multiples

f(R) - f(L-1)を求めるやつ
制約が小さいので全探索でいい
提出コード

void solve(){
    int L, R, D;
    cin >> L >> R >> D;
    int ans = 0;
    for(int i=L;i<=R;i++) if(i % D == 0) ans++;
    cout << ans << endl;
}

B - An Odd Problem

iとa_iがどちらも奇数のものをカウントする
提出コード

void solve(){
    int N;
    cin >> N;
    vector<int> a(N+1);
    int ans = 0;
    for(int i=1;i<=N;i++){
        cin >> a[i];
        if((i & 1) && (a[i] & 1)) ans++;
    }
    cout << ans << endl;
}

C - XYZ Triplets

x^2を考えるとx = 100のときx^2 = 10^4になるので
1 \leq x, y, z \leq 100程度で全探索すればいい
提出コード

void solve(){
    int N;
    cin >> N;
    vector<int> cnt(N+10);
    for(ll i=1;i<=300;i++){
        for(ll j=1;j<=300;j++){
            for(ll k=1;k<=300;k++){
                ll x = i*i + j*j + k*k + i*j + j*k + k*i;
                if(x > N) continue;
                cnt[x]++;
            }
        }
    }
    for(int i=1;i<=N;i++) cout << cnt[i] << endl;
}

D - Anything Goes to Zero

最初の1回目の操作を考えると最大でも2 \times 10^5で割った余りを求めるので、一回目の操作の値を求めることが出来れば、後は愚直に操作が出来る
1回の操作でpopcount(X)の値はpopcount(X) \pm 1の2通りしか無いのでX mod (popcount(X) \pm 1)を前計算しておく
そうすると、一回目の操作後の値は、そのbitを反転させたときの差分と、前計算した2通りのどちらかのmodを使って求めることが出来る
二回目以降は愚直に操作をすればいい
ただし、操作を行ったときに0になる時の場合分けが必要
提出コード

void solve(){
    int N;
    string S;
    cin >> N >> S;
    int cnt = 0;
    reverse(S.begin(), S.end());
    REP(i,N) if(S[i] == '1') cnt++;
    ll x1 = 0, x2 = 0;
    REP(i,N){
        if(S[i] == '1'){
            if(cnt > 1){
                x1 += mod_pow(2, i, cnt-1);
                x1 %= (cnt - 1);
            }
            x2 += mod_pow(2, i, cnt+1);
            x2 %= (cnt + 1);
        }
    }
    vector<int> ans(N);
    REP(i,N){
        if(S[i] == '1'){
            if(cnt == 1){
                ans[i] = 0;
                continue;
            }
            ll tmp = x1 - mod_pow(2, i, cnt - 1) + (cnt - 1);
            tmp %= (cnt - 1);
            ans[i]++;
            while(tmp > 0){
                ans[i]++;
                tmp %= __builtin_popcount(tmp);
            }
        }
        else{
            ll tmp = x2 + mod_pow(2, i, cnt+1);
            tmp %= (cnt + 1);
            ans[i]++;
            while(tmp > 0){
                ans[i]++;
                tmp %= __builtin_popcount(tmp);
            }
        }
    }
    reverse(ans.begin(), ans.end());
    REP(i,N) cout << ans[i] << endl;
}

E - Camel Train

L_i \geq R_iとL_i \lt R_iに分けて考える
前者は出来るだけ左側に寄せて、後者は出来るだけ右側に寄せた方がお得
後者より右側に前者が存在する場合、その部分を入れ替えても損をすることは無いので、それぞれ独立に考えても良いことがわかる
前者を考えると、どの位置においても最低R_iは得られる
ラクダiがK_i番目以内にいる時、L_i - R_iが追加で得られる
そうすると、制約がきついほうから考えると左側から順にi = K_jとなるようなラクダのL_j - R_jをpriority_queueに入れていき、size(pq) > iなら小さい方から取り除いていき、残ったものの総和を加算する
後者の場合も同様に右側から順に処理をしていき、最後に残ったものの総和を加算する
提出コード

void solve(){
    int N;
    cin >> N;
    vector<vector<ll>> vp(N+10), vm(N+10);
    ll ans = 0;
    int cnt = 0;
    REP(i,N){
        int K, L, R;
        cin >> K >> L >> R;
        if(L >= R){
            vp[K].emplace_back(L - R);
            ans += R;
            cnt++;
        }
        else{
            ans += L;
            vm[K].emplace_back(R - L);
        }
    }

    priority_queue<ll, vector<ll>, greater<ll>> pq, pq2;
    for(int i=1;i<=N;i++){
        for(auto x : vp[i]) pq.emplace(x);
        while(size(pq) > i) pq.pop();
    }
    while(!pq.empty()) ans += pq.top(), pq.pop();

    for(int i=N;i>=1;i--){
        for(auto x : vm[i]) pq2.emplace(x);
        while(size(pq2) > N - i) pq2.pop();
    }
    while(!pq2.empty()) ans += pq2.top(), pq2.pop();
    cout << ans << endl;
}