ABC 400

Sat, Apr 5, 2025

C. 2^a b^2

https://atcoder.jp/contests/abc400/tasks/abc400_c

AC したがなぜ AC したのかよくわからず AC した。sqrt が誤差を生むので出てきた数の周辺で検算をするようにして AC したが知識がないとsqrt を使ったときに落とせるテストケースもかけないのでかなり難しい問題に感じた。

$2^a$ を動かして取りうる $b^2$ の個数を求める方法だと $X = 16 = 2^2 \times 2^2 = 2^4 \times 1^2$ のように同じ数に対して重複してカウントしてしまうことがある。

2の冪はすべて $2^a$ の方に押し込んで、$b$ は奇数という制約をかけると重複しない。

\begin{align*} 2^k \times b^2 \leq N &\Rightarrow b^2 \leq N / 2^k \\ &\Rightarrow b \leq \sqrt{N/2^k} \\ &\Rightarrow b \leq \lfloor \sqrt{N/2^k} \rfloor ~~~(\because b \text{ is an integer}) \end{align*}

であり $[1, \lfloor \sqrt{N/2^k} \rfloor]$ に含まれる奇数の個数は $\displaystyle \left\lfloor \frac{\lfloor \sqrt{N/2^k} \rfloor + 1}{2} \right\rfloor$ である。

よって問題の制約では

\begin{align*} \sum_{k=1}^{60} \left\lfloor \frac{\lfloor \sqrt{N/2^k} \rfloor + 1}{2} \right\rfloor \end{align*}

を求めれば良い。($2^{60} > 10^{18}$ なので $k=59$ までで十分だが $k=60$ までループを回しても $\lfloor N/2^{60} \rfloor = 0$ なので $k=60$ までしても問題ない)

ここで sqrt を使うと誤差が出るので sqrtl を使うといいらしい。たとえば $N = 2^{52} + 2^{27} = 4503599761588224$ のとき (long long int)sqrt(N) = 67108865 を返すが $67108865^2 = 4503599761588225 > N$ となる。 bit 演算で平方根を求める方法もあるらしい

ref:

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

    ll N;
    cin >> N;
    ll ans = 0;

    rep2(i, 1, 61) {
        ll x = sqrtl((long double)N / (1ll << i));
        ans += (x + 1) / 2;
    }
    cout << ans << endl;
}

別解

$N$ 以下の数を素因数分解したときに 2 の指数部が偶数か奇数かで場合分けする。

偶数のとき

$2^2 \times b^2 \leq N \Rightarrow b^2 \leq N/4 \Rightarrow b \leq \lfloor \sqrt{N/4} \rfloor$

より $N$ 以下の数のうち素因数2の指数部が偶数のものは $\lfloor \sqrt{N/4} \rfloor$ 個存在する

奇数のとき

$2^1 \times b^2 \leq N \Rightarrow b^2 \leq N/2 \Rightarrow b \leq \lfloor \sqrt{N/2} \rfloor$

より $N$ 以下の数のうち素因数2の指数部が奇数のものは $\lfloor \sqrt{N/2} \rfloor$ 個存在する

以上より求める答えは $\lfloor \sqrt{N/4} \rfloor + \lfloor \sqrt{N/2} \rfloor$.

ll isqrt(ll x) {
    ll ac = 0, wa = (ll)1e9 + 7;
    while (wa - ac > 1) {
        ll wj = (wa + ac) / 2;
        if (wj * wj <= x)
            ac = wj;
        else
            wa = wj;
    }

    return ac;
}

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

    ll N;
    cin >> N;
    cout << isqrt(N / 2) + isqrt(N / 4) << endl;
}

D. Takahashi the Wall Breaker

https://atcoder.jp/contests/abc400/tasks/abc400_d

道に進むときはコスト0で移動。壁を壊して進む場合はコスト1で移動。2個先に移動する場合は途中か行き先が壁ならばコスト1で移動。このコストでダイクストラをすればよい。

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

    int H, W;
    cin >> H >> W;
    vector<string> grid(H);
    rep(i, H) cin >> grid[i];

    int A, B, C, D;
    cin >> A >> B >> C >> D;
    A--, B--, C--, D--;

    vint di = {1, 0, -1, 0};
    vint dj = {0, -1, 0, 1};

    vint graph(H * W);
    // cnt, position
    using P = pair<ll, pair<int, int>>;
    priority_queue<P, vector<P>, greater<P>> pq;
    pq.push({0, {A, B}});
    vvll dist(H, vll(W, INF));
    dist[A][B] = 0;

    while (pq.size()) {
        auto [cost, now] = pq.top();
        pq.pop();
        auto [i, j] = now;

        if (dist[i][j] < cost)
            continue;

        rep(d, 4) {
            int wall = 0;
            for (int k = 1; k <= 2; k++) {
                int ni = i + di[d] * k, nj = j + dj[d] * k;
                if (clamp(ni, 0, H - 1) != ni || clamp(nj, 0, W - 1) != nj)
                    continue;
                wall = wall || grid[ni][nj] == '#';
                ll w = cost + wall;
                if (dist[ni][nj] > w) {
                    dist[ni][nj] = w;
                    pq.push({w, {ni, nj}});
                }
            }
        }
    }

    cout << dist[C][D] << endl;
}

別解

ダイクストラ使わずとも 01-BFS なる手法でも解けるらしい。 priority queue の代わりに deque を使う。queue の中に入っている要素間の差は最大でも1なのでコスト0の移動のときは queue の先頭に、コスト1の移動のときは queue の末尾に push するだけで十分。ダイクストラよりも高速に動く

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

    int H, W;
    cin >> H >> W;
    vector<string> grid(H);
    rep(i, H) cin >> grid[i];

    int A, B, C, D;
    cin >> A >> B >> C >> D;
    A--, B--, C--, D--;

    vint di = {1, 0, -1, 0};
    vint dj = {0, -1, 0, 1};

    vint graph(H * W);
    // cnt, position
    using P = pair<ll, pair<int, int>>;
    deque<P> deq;
    deq.push_back({0, {A, B}});
    vvll dist(H, vll(W, INF));
    dist[A][B] = 0;

    while (deq.size()) {
        auto [cost, now] = deq.front();
        deq.pop_front();
        auto [i, j] = now;

        if (dist[i][j] < cost)
            continue;

        rep(d, 4) {
            int wall = 0;
            for (int k = 1; k <= 2; k++) {
                int ni = i + di[d] * k, nj = j + dj[d] * k;
                if (clamp(ni, 0, H - 1) != ni || clamp(nj, 0, W - 1) != nj)
                    continue;
                wall = wall || grid[ni][nj] == '#';
                ll w = cost + wall;
                if (dist[ni][nj] > w) {
                    dist[ni][nj] = w;
                    if (wall) {
                        deq.push_back({w, {ni, nj}});
                    } else {
                        deq.push_front({w, {ni, nj}});
                    }
                }
            }
        }
    }

    cout << dist[C][D] << endl;
}

E. Ringo’s Favorite Numbers 3

https://atcoder.jp/contests/abc400/tasks/abc400_e

$X$ を $A$ 以下の最大の 400 number とする。条件より素数 $p$, $q$, 非負整数 $a$, $b$ を用いて $X = p^{2a}q^{2b}$ と表せる。

$p^{2a}q^{2b} \leq A \leq 10^{12} \Rightarrow p^a q^b \leq 10^6$ であるから 400 number の平方根の数は $10^6$ 個以下である。すなわち 400 number の個数も $10^6$ 個以下である。

$10^6$ 以下の数字の中から素因数分解して素因数の個数が2であるものが 400 number の平方根であり、その2乗が 400 number である。考えうる 400 number をすべて列挙しておき、$A$ 以下の 400 number のうち最大のものを二分探索で求める。

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

    vll sieve((int)1e6 + 5, -1);
    rep2(i, 2, (int)1e6 + 5) {
        for (ll j = i; j < (int)1e6 + 5; j += i) {
            if (sieve[j] < 0)
                sieve[j] = i;
        }
    }

    auto factor = [&](ll x) -> vector<pair<ll, ll>> {
        vector<pair<ll, ll>> ans;
        while (x > 1) {
            ll p = sieve[x];
            ll cnt = 0;
            while (x % p == 0) {
                cnt++;
                x /= p;
            }

            ans.push_back({p, cnt});
        }

        return ans;
    };

    vll memo;
    rep2(i, 6, (int)1e6 + 5) {
        auto ret = factor(i);
        if (ret.size() != 2)
            continue;

        ll ans = 1;
        for (auto [x, cnt] : ret) {
            ans *= intpow(x, cnt);
        }
        memo.push_back(-ans * ans);
    }
    reverse(all(memo));

    auto cal = [&](ll x) -> void {
        ll t = -*lower_bound(all(memo), -x);
        cout << t << endl;
    };

    int n;
    cin >> n;
    rep(i, n) {
        ll x;
        cin >> x;
        cal(x);
    }
}

解説コードの解説

$10^6$ 以下の数のうち素因数の個数が2という情報だけが必要で指数部の情報は重要ではないので、エラトステネスのふるいの要領で素因数の個数を調べた後に素因数の個数が2となっているものが 400 number の平方根である。

昇順で並べられた配列の中から $x$ 以下のうち最大のものを求める場合 prev(upper_bound()) で求められるというのが目からウロコだった。

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

    ll mx = (int)1e6 + 5;
    // numprime[i]: 数字 i の素因数の数
    vll numprime(mx, 0);
    rep2(i, 2, mx) {
        if (numprime[i] == 0) {
            for (ll j = i; j < mx; j += i) {
                numprime[j]++;
            }
        }
    }

    // 10^18 以下の 400 number
    vll n400;
    rep(i, mx) {
        if (numprime[i] == 2) {
            n400.push_back(i * i);
        }
    }

    auto cal = [&](ll x) -> void {
        ll ans = *prev(upper_bound(all(n400), x));
        cout << ans << endl;
    };

    int n;
    cin >> n;
    rep(i, n) {
        ll x;
        cin >> x;
        cal(x);
    }
}

ABC 400

Table of Contents

C. 2^a b^2

別解

D. Takahashi the Wall Breaker

別解

E. Ringo’s Favorite Numbers 3

解説コードの解説