ABC 406

Sun, May 18, 2025

B - Product Calculator

多倍長整数の問題を C++ で解くと時間がかかりそうだったので、コンテスト中は Python で解いた

$a$, $X$, $Y$ が整数のとき、$aX > Y \Leftrightarrow X > \floor{\frac{Y}{a}}$ となるので $Y = 10^K - 1$, $X$ を表示されている数としたとき、$X > \floor{\frac{Y}{a}}$ なら $X = 1$ とし、そうでないならば $X$ に $a$ を掛ける。

def main():
    n, k = map(int, input().split())
    a = map(int, input().split())

    mx = 10**k
    ans = 1
    for i in a:
        ans *= i
        if ans >= mx:
            ans = 1

    print(ans)

main()

ll intpow(ll x, ll n) {
    long long ret = 1;
    while (n > 0) {
        if (n & 1)
            ret *= x;
        x *= x;
        n >>= 1;
    }
    return ret;
}

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    ll N, K;
    cin >> N >> K;
    vll A(N);
    rep(i, N) cin >> A[i];

    ll mx = intpow(10, K) - 1;
    ll ans = 1;
    for (ll a : A) {
        if (ans > mx / a) {
            ans = 1;
        } else {
            ans *= a;
        }
    }
    cout << ans << endl;
}

C - ~

/\/\/... といった形のように数字が上下振れているところから /\/ の部分に着目して個数を数えていく。

まず極値を取る index を配列 $X$ に格納する。端点も極値であるとする。このとき、一番はじめの要素は local minimum であるようにする。 $i$ 番目が local minimum であるとき、$i+1$ 番目の要素は local maximum、$i+2$ 番目の要素は local minimum、$i+3$ 番目の要素は local maximum である。このとき、両端を動かしてもチルダ型の形を保つ場合があり、そのような場合の数は $(X_{i+1} - X_i) \times (X_{i+3} - X_{i+2})$ 通りである。

これを全ての local minimum となる $i$ に対して計算し総和を求める。

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    ll N;
    cin >> N;
    vll P(N);
    rep(i, N) cin >> P[i];

    int s = -1;
    rep(i, N - 1) {
        if (P[i] < P[i + 1]) {
            s = i;
            break;
        }
    }
    if (s < 0) {
        cout << 0 << endl;
        return;
    }

    vll ids;
    ids.push_back(s);
    rep2(i, s + 1, N) {
        if (i - 1 >= 0 && i + 1 < N) {
            if (P[i - 1] < P[i] && P[i] > P[i + 1])
                ids.push_back(i);
            if (P[i - 1] > P[i] && P[i] < P[i + 1])
                ids.push_back(i);
        }
    }
    if (P[N - 2] < P[N - 1])
        ids.push_back(N - 1);

    ll ans = 0;
    int M = ids.size();
    rep(i, M) {
        if (i % 2 == 1)
            continue;
        if (i + 3 < M) {
            ans += (ids[i + 1] - ids[i]) * (ids[i + 3] - ids[i + 2]);
        }
    }
    cout << ans << endl;
}

D - Garbage Removal

$A_i$ を $i$ 行目にあるゴミの列番号を保存した集合、$B_j$ を $j$ 列目にあるゴミの行番号を保存した集合とする。

タイプ1のとき、$A_x$ のサイズを出力しする。出力したあと $y \in A_x$ なる $y$ に対して $B_y$ から $x$ を削除する。 $A_x$ を空集合にする。

タイプ2のときも同様に処理する。

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    ll H, W, N;
    cin >> H >> W >> N;
    vector<pair<ll, ll>> dust(N);
    rep(i, N) {
        ll x, y;
        cin >> x >> y;
        x--, y--;
        dust[i] = {x, y};
    }

    vector<set<int>> A(H), B(W);
    for (auto [x, y] : dust) {
        A[x].insert(y);
        B[y].insert(x);
    }

    ll Q;
    cin >> Q;
    rep(_, Q) {
        ll t, z;
        cin >> t >> z;
        z--;

        if (t == 1) {
            cout << A[z].size() << '\n';
            for (ll y : A[z]) {
                B[y].erase(z);
            }
            A[z] = set<int>();
        } else {  // t == 2
            cout << B[z].size() << '\n';
            for (ll x : B[z]) {
                A[x].erase(z);
            }
            B[z] = set<int>();
        }
    }
}

E - Popcount Sum 3

事前準備

$f(d, k)$ を $2^d$ 未満の popcount が $k$ の数の総和とする。 $i$ bit 目が立っているような $2^d$ 未満の popcount が $k$ となるような数の個数は $i$ bit 目以外の $d-1$ 箇所の中から $k-1$ 箇所を選ぶ組み合わせの数であるので $\binom{d-1}{k-1}$ 通りある。 $0 \sim d-1$ bit 目についても同様に $\binom{d-1}{k-1}$ 通りあるので

\begin{align*} f(d, k) &= \left(\sum_{i=0}^{d-1} 2^i \right) \cdot \binom{d-1}{k-1} \\ &= (2^d - 1) \binom{d-1}{k-1} \end{align*}

実際に計算する

$N$ 未満の popcount が $K$ となる数の総和について考える。各 bit が立っている部分についてその部分がどれだけ答えに寄与するかを考える。

$m = \mathrm{popcount}(N)$ のとき、bit が立っている場所のうち下位 bit 側から数えて $i$ 番目(0-index)を $d_i$ とすると $N = \sum_{i=0}^{m-1} 2^{d_i}$ と書ける。

$d_i$ bit 目が立っているか折れているかで場合分け

$d_i$ bit 目が折れているとき

$d_{m-1}$ bit 目が折れているとき、$0 \sim d_{m-1} - 1$ bit 目をどんなふうにしても $N$ よりかは大きくならないので、$f(d_{m-1}, K)$ がまず答えに寄与する。

$d_{m-1}$ bit 目が立っていて $d_{m-2}$ bit 目が折れているとき、$0 \sim d_{m-2} - 1$ bit 目をどんなふうにしても $N$ よりかは大きくならないので、$f(d_{m-2}, K-1)$ が答えに寄与する。

どうようにして $d_{m-1}, \cdots, d_{m-j}$ bit 目が立っていて $d_{m-j-1}$ bit 目が折れているとき、$0 \sim d_{m-j-1} - 1$ bit 目をどんなふうにしても $N$ よりかは大きくならないので、$f(d_{m-j-1}, K-j)$ が答えに寄与する。

よって $d_i$ bit 目が折れているときの $2^{d_i}$ 未満の寄与の総和は

\begin{align*} \sum_{j=0}^{m-1} f(d_{m-j-1}, K-j) \end{align*}

$d_i$ bit 目が立っているとき

$d_{m-1}$ bit 目が立っているとき、$d_{m-1}$ bit 目が立っていて、かつ、$N$ 未満の数で popcount が $K$ となるような場合の数がわかると $2^{d_{m-1}}$ が答えにどれだけ寄与するかわかる。

$d_{m-2}$ bit 目が折れているとき、$0 \sim d_{m-2} - 1$ bit 目をどんなふうにしても $N$ 未満になるから、 $\binom{d_{m-2}}{K-1}$ 通りある。 $d_{m-1}, d_{m-2}$ bit 目が立っており、$d_{m-3}$ bit 目が折れているとき、$0 \sim d_{m-3} - 1$ bit 目をどんなふうにしても $N$ 未満になるから、 $\binom{d_{m-3}}{K-2}$ 通りある。

これを繰り返していくと、$2^{d_{m-1}}$ の寄与は

\begin{align*} 2^{d_{m-1}} \cdot \sum_{i=1}^{m-1} \binom{d_{m-i-1}}{K-i} \end{align*}

これを全ての $d_i$ bit 目についても求めると

\begin{align*} \sum_{i=0}^{m-1} 2^{d_{m-i-1}} \cdot \sum_{j=i+1}^{m-1} \binom{d_{m-j-1}}{K-j} \end{align*}

最終結果

$N$ 未満の popcount が $K$ となる数の総和を

\begin{align*} S = \sum_{i=0}^{m-1} f(d_{m-i-1}, K-i) + \sum_{i=0}^{m-1} 2^{d_{m-i-1}} \cdot \sum_{j=i+1}^{m-1} \binom{d_{m-j-1}}{K-j} \end{align*}

とすると、$K = \mathrm{popcount}(N)$ の場合 $S + N$, そうでない場合は $S$ となる。

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int mx = 65;
    vector<mint> fac(mx), invfac(mx);
    fac[0] = invfac[0] = 1;
    rep2(i, 1, mx) {
        fac[i] = fac[i - 1] * i;
    }
    rep2(i, 1, mx) {
        invfac[i] = fac[i].inv();
    }

    auto choose = [&](int n, int k) -> mint {
        if (n < 0 || k < 0 || n < k)
            return 0;
        return fac[n] * invfac[n - k] * invfac[k];
    };

    auto f = [&](ll i, ll K) -> mint {
        // 2^i 未満の popcount K の数の総和
        mint tot = (1ll << i) - 1;
        return tot * choose(i - 1, K - 1);
    };

    auto cal = [&]() -> void {
        ll N, K;
        cin >> N >> K;

        vint ids;
        rep(i, 61) if ((N >> i) & 1) ids.push_back(i);
        reverse(all(ids));

        mint ans = 0;
        if (__builtin_popcountll(N) == K)
            ans += N;

        int m = ids.size();
        rep(i, m) {
            // kill ids[i] th bit
            ans += f(ids[i], K - i);

            // ids[i] th bit alive
            rep2(j, i + 1, m) {
                // kill ids[j] bit
                ans += choose(ids[j], K - j) * (1ll << ids[i]);
            }
        }
        cout << ans.val() << endl;
    };

    int t;
    cin >> t;
    rep(_, t) {
        cal();
    }
}