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

問題

感想

4完だったけど、ちょっと早かったので久しぶりに温まった。やったね！

最近のABC難しすぎひんか？？？5完以上できない回が続いてる。

平成ABCの傾斜に近いという声もあったが、確かにそんな感じがする。

やったぜ！
scolさんのエイシングプログラミングコンテスト 2020での成績：538位
パフォーマンス：1803相当
レーティング：1505→1538 (+33) :)#AtCoder #エイシングプログラミングコンテスト2020 https://t.co/usSZEqWoM2
— スコル (@scol_kp) 2020年7月11日

A - Number of Multiples

$O(1)$ でも解けるけど、脳死で全探索を書くのが速い。

提出コード

リンク： https://atcoder.jp/contests/aising2020/submissions/15142182

void solve() {
    ll L, R, D;
    cin >> L >> R >> D;
    ll ans = 0;
    for (ll i = L; i <= R; i++) {
        if (i % D == 0) {
            ++ans;
        }
    }
    cout << ans << "\n";
}

B - An Odd Problem

前から丁寧に確かめていく。

提出コード

リンク：https://atcoder.jp/contests/aising2020/submissions/15146652

void solve() {
    ll N;
    cin >> N;
    Vl A(N + 1);
    for (ll i = 1; i <= N; i++) {
        cin >> A[i];
    }
    ll ans = 0;
    for (ll i = 1; i <= N; i++) {
        if (i & 1 && A[i] & 1) {
            ++ans;
        }
    }
    cout << ans << "\n";
}

C - XYZ Triplets

10分くらい解法が思いつかなかった。因数分解できることを願ってWolframAlphaに投げたら

僕「x² + y² + z² + xy + yz + zx を因数分解するとどうなりますか？」

Wolframくん「x² + y² + z² + xy + yz + zx を因数分解すると x² + y² + z² + xy + yz + zx になります。」

僕「そう......」

という悲しい思いをした。で、制約と式をよく見ると、 $1 \le x,y,z \le 100$ のみを考えれば良いことに気づき、全探索を書いてACを得た。全探索で行けるかどうかぐらいは最初に確認しましょう（笑）。このとき、順位表を見ると2000位くらいで冷や汗をかいた。

提出コード

リンク：https://atcoder.jp/contests/aising2020/submissions/15158903

void solve() {
    ll N;
    cin >> N;
 
    Vl cnts(N + 1);
    for (ll i = 1; i <= 100; i++) {
        for (ll j = 1; j <= 100; j++) {
            for (ll k = 1; k <= 100; k++) {
                ll t = i * i + j * j + k * k + i * j + j * k + k * i;
                if (t > N) continue;
                ++cnts[t];
            }
        }
    }
 
    for (ll i = 1; i <= N; i++) {
        cout << cnts[i] << "\n";
    }
}

D - Anything Goes to Zero

$\mathrm{popcount}(n) \le \lfloor \log_{2} n \rfloor + 1$ なので、操作はすぐに終了することがわかる。各操作さえ高速に処理できればそのままシミュレートしてもよさそうだな～～という気持ちになる。

で、操作を実装しようとしたときに一つ問題がでてきて、1回目の操作が厄介なことに気づく。 2²⁰⁰⁰⁰⁰ くらいの超巨大な数の剰余を求めなければならない。 2回目以降は 32bit 整数の範囲でふつうに計算できる。

$f(X_1), \ldots, f(X_N)$ を愚直に求めようとすると、1回目の操作、すなわち、超巨大な数の剰余を求めることを最大で 200000 回くらいしなければならない。これは間に合わない。

落ち着いて考えると、 $X_i = X + 2^{N - i}$ or $X_i = X - 2^{N - i}$ であって、また、 $X$ も $2^k$ の和で表されるから、 $2^0, 2^1, \ldots, 2^{N-1}$ を $\mathrm{popcount}(X) + 1$ または $\mathrm{popcount(X) - 1}$ で割ったときの余りを前計算しておけば、差分計算によって、各 $X_i$ における1回目の操作の結果を高速に求めることができる。

また、 $X$ のビットが1つしか立ってないとき、操作を全くしないことがあるので、実装時にはそれに気を付ける必要がある。（これにちゃんと気づけた。えらい！！）

これACできたとき、天才！！！ってなったけど、コンテストが終わってみると結局1500人も解いていた......。天才が1500人いたということやな！！競プロ界、天才が多すぎる。

提出コード

リンク：https://atcoder.jp/contests/aising2020/submissions/15167363

using bs = bitset<200010>;
 
void solve() {
    ll N;
    cin >> N;
    string S;
    cin >> S;
 
    bs base;
    for (ll i = 0; i < N; i++) {
        if (S[i] == '1') {
            base[N - 1 - i] = true;
        }
    }
 
    ll pcnt = base.count();
    ll pcnt1 = pcnt + 1;
    ll pcnt2 = pcnt - 1;
    if (pcnt2 == 0) {
        pcnt2 = -1;
    }
    Vl rs1(N), rs2(N);
    ll cur1 = 1;
    ll cur2 = 1;
    for (ll i = 0; i < N; i++) {
        rs1[i] = cur1;
        cur1 *= 2;
        cur1 %= pcnt1;
 
        rs2[i] = cur2;
        cur2 *= 2;
        cur2 %= pcnt2;
    }
 
    //+
    ll r1 = 0;
    for (ll i = 0; i < N; i++) {
        if (base[i]) {
            r1 += rs1[i];
        }
    }
    r1 %= pcnt1;
 
    //-
    ll r2 = 0;
    for (ll i = 0; i < N; i++) {
        if (base[i]) {
            r2 += rs2[i];
        }
    }
    r2 %= pcnt2;
 
    for (ll i = N - 1; i >= 0; i--) {
        if (pcnt == 1 && base[i]) {
            cout << 0 << "\n";
            continue;
        }
 
        ll r;
        if (base[i]) {
            r = (r2 - rs2[i] + pcnt2) % pcnt2;
        }
        else {
            r = (r1 + rs1[i]) % pcnt1;
        }
 
        ll cnt = 1;
        while (r > 0) {
            ll c = __builtin_popcountll(r);
            r %= c;
            ++cnt;
        }
 
        cout << cnt << "\n";
    }
}