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

A - Number of Multiples

問題へのリンク

解説

愚直にfor文でいいですが、以下のの倍数の個数はX割るd（切り捨て）で求められるので、それを利用してもいいかもしれません。

実装

int main(){
    int l, r, d;
    cin >> l >> r >> d;
    cout << r / d - (l-1) / d << endl;
}

B - An Odd Problem

問題へのリンク

解説

言われた通り実装しましょう。

実装

int main() {
    int N;
    cin >> N;
    vector<ll> A(N);
    rep(i, N)cin >> A[i];
    ll ans = 0;
    rep(i,N){
        if(A[i] % 2 == 1 && i % 2 == 0)ans++;
    }
    cout << ans << endl;
}

C - XYZ Triplets

問題へのリンク

解説

一瞬数学かと思って因数分解しかけましたが、制約を見ると100まで見れば十分であることがわかるので、三重for文をクエリの外で回します。

実装

int main() {
    ll N;
    cin >> N;
    map<ll,int> mp;
    for(ll x = 1; x <= 100; x++){
        for(ll y = 1; y <= 100; y++){
            for(ll z = 1; z <= 100; z++){
                mp[(x*y + y*z + z*x)+x*x + y*y + z*z]++;
            }
        }
    }
    for(int n = 1; n <= N; n++){
        cout << mp[n] << endl;
    }
}

D - Anything Goes to Zero

問題へのリンク

解説

これハマってしまった。本番は大きい数の割り算を自前で実装しようとして破滅しました。桁ごとに見ればいいことに気づけませんでした。また、必要なmodは2種類のみなので、桁ごとに前計算しておけばいいです。

1回目の操作に毎回かけるとTLEしてしまいますが、差分だけを計算するために入力のについて計算しておいて、適宜+-すれば1回目はでできます。2回目以降は割られる数が以下になるので、割り算を毎回しても間に合います。再帰を使っていい感じに書きましょう。

コーナーケースは、一回も操作しないで良い状態、つまりから始まる場合です。

実装

// cnt + 1, cnt - 1
ll beki[2][200010];
ll ans[200010];
ll f(ll X, int cnt = 1){
    if(X == 0)return cnt;
    ll M = __builtin_popcount(X);
    return f(X%M, cnt+1);
}
int main() {

    ll N;
    string X;
    cin >> N >> X;
    reverse(all(X));
    int cnt = 0;
    rep(i,N)cnt += X[i] == '1';
    ll tmp = 1;
    rep(i,N){
        beki[0][i] = tmp % (cnt+1);
        tmp *= 2;
        tmp %= (cnt+1);
    }
    tmp = 1;
    rep(i,N){
        if(cnt - 1 == 0){
            beki[1][i] = -1;
            continue;
        }
        beki[1][i] = tmp % (cnt - 1);
        tmp *= 2;
        tmp %= (cnt - 1);
    }
    ll X0[2] = {0,0};
    rep(j,2){
        ll M = cnt;
        if(j == 0)M++;
        else M--;
        rep(i,N){
            if(M == 0)break;
            if(X[i] == '1')X0[j] += beki[j][i];
            X0[j] %= M;
        }
    }
    rep(i,N){
        ll M = cnt;
        ll tmpX;
        if(X[i] == '1'){
            M--;
            if(M == 0){
                ans[i] = 0;
                continue;
            }
            tmpX = X0[1];
            tmpX -= beki[1][i];
            tmpX += M;
            tmpX %= M;
        }
        else{
            M++;
            tmpX = X0[0];
            tmpX += beki[0][i];
            tmpX %= M;
        }
        ans[i] = f(tmpX);
    }
    rep(i,N){
        cout << ans[N-1-i] << endl;
    }
}

E - Camel Train

問題へのリンク

記事を分けました

coonevo.hatenablog.com

F - Two Snuke

問題へのリンク

まだ見てません。