ABC 445

Sat, Feb 14, 2026

A. Strong Word

https://atcoder.jp/contests/abc445/tasks/abc445_a

2026/2/14 コンテスト中に自力 AC

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

    string S;
    cin >> S;
    yesno(S[0] == S.back());
}

B. Center Alignment

https://atcoder.jp/contests/abc445/tasks/abc445_b

2026/2/14 コンテスト中に自力 AC

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

    ll N;
    cin >> N;
    vector<string> S(N);
    rep(i, N) cin >> S[i];

    ll m = 0;
    rep(i, N) chmax(m, (ll)S[i].size());

    for (string s : S) {
        string ans = string(m, '.');
        int len = (m - s.size()) / 2;
        rep(i, (ll)s.size()) {
            ans[len + i] = s[i];
        }
        cout << ans << '\n';
    }
}

C. Sugoroku Destination

https://atcoder.jp/contests/abc445/tasks/abc445_c

2026/2/14 コンテスト中に自力 AC

コンテスト中は $i \leq A_i \leq N$ という条件を見落としていて無理やりダブリングで通した。 Julia で $10^{100}$ の2のべき乗展開して無理やりダブリングで通したが配列を使い回すなどしてメモリを節約してどうにか通した。

公式解説読んでダブリングの要領で $10^i$ 回の操作後の位置を求めるテーブルを作る方法が上記の制約について気にせずに実装も楽で良さそうだった。

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

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

    // tens[i][j]: j にあるコマが 10^i の操作後にいる場所
    vvll tens(101, vll(N));
    tens[0] = A;

    rep2(i, 1, 101) {
        rep(j, N) {
            ll now = tens[i - 1][j];
            rep2(k, 1, 10) {
                now = tens[i - 1][now];
            }
            tens[i][j] = now;
        }
    }

    vll ans;
    rep(i, N) {
        ans.push_back(tens[100][i] + 1);
    }
    print(ans);
}

$i \leq A_i \leq N$ という条件より、留まるか右に移動するかの2択しかないので最大でも $N-1$ 回の操作以降は位置が変わらない。

後ろから位置が確定していくので、後ろから順に位置を更新していけば $O(N)$ で求めることができる。

コンテスト後に解説読んで解いた方法

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

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

    vll ans(N);
    iota(all(ans), 0ll);
    for (int i = N - 2; i >= 0; i--) {
        ans[i] = ans[A[i]];
    }

    rep(i, N) ans[i]++;
    print(ans);
}

無理やりダブリングで通した方法

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

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

    // 10^100 の2進数表記
    string ten_handred = "100100100100110101101001001011001010011000011011111001110101100001011001001111000010011000100110011100000101111110011100010101100111001000000100011100010000100011010011111001010101010110010010000110000100010101000001011101000111100010000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000";

    int M = ten_handred.size();

    vll now(N);
    vll d = A, dn(N);
    iota(all(now), 0);
    rep(i, M) {
        rep(j, N) {
            ll nx = d[d[j]];
            dn[j] = nx;
        };
        swap(d, dn);
        if (ten_handred[i] == '0') continue;
        rep(j, N) {
            now[j] = d[now[j]];
        }
    }

    rep(i, N) now[i]++;
    print(now);
}

D. Reconstruct Chocolate

https://atcoder.jp/contests/abc445/tasks/abc445_d

2026/2/14 コンテスト中に自力 AC

ピースを $H \times W$ の領域に配置していくことを考える。

ピースの作成方法から、ピースの置かれていない領域の縦か横の長さと一致するピースが少なくても一つは存在する。いずれかに縦か横の長さが一致するピースがあればそれを領域の左上に配置していくことで条件を満たす配置ができる。

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

    ll H, W, N;
    cin >> H >> W >> N;
    using P = pair<ll, ll>;
    vector<P> chocos(N);
    rep(i, N) {
        ll h, w;
        cin >> h >> w;
        chocos[i] = {h, w};
    }

    ll r = 0, c = 0;

    // h,w,index
    using T = tuple<ll, ll, ll>;
    vector<T> rows(N), cols(N);
    rep(i, N) {
        rows[i] = cols[i] = {chocos[i].first, chocos[i].second, i};
    }

    auto opr = [](const T& a, const T& b) -> bool {
        auto [ar, ac, ai] = a;
        auto [br, bc, bi] = b;
        return ar > br;
    };
    auto opc = [](const T& a, const T& b) -> bool {
        auto [ar, ac, ai] = a;
        auto [br, bc, bi] = b;
        return ac > bc;
    };
    sort(all(rows), opr);
    sort(all(cols), opc);

    vint used(N);

    int ri = 0, ci = 0;

    vector<pair<ll, ll>> ans(N);

    rep(i, N) {
        while (ri < N) {
            auto [h, w, id] = rows[ri];
            if (!used[id]) break;
            ri++;
        }
        while (ci < N) {
            auto [h, w, id] = cols[ci];
            if (!used[id]) break;
            ci++;
        }

        if (ri < N) {
            auto [h, w, id] = rows[ri];
            if (H - r == h) {
                ans[id] = {r + 1, c + 1};
                c += w;
                used[id] = 1;
                continue;
            }
        }
        if (ci < N) {
            auto [h, w, id] = cols[ci];
            if (W - c == w) {
                ans[id] = {r + 1, c + 1};
                r += h;
                used[id] = 1;
            }
        }
    }

    for (auto [x, y] : ans) cout << x << ' ' << y << '\n';
}

E. Many LCMs

https://atcoder.jp/contests/abc445/tasks/abc445_e

2026/2/14 解説 AC 方針はわかったが計算量を落とすことができなかった。

定数倍を落とさないといけなかったらしい。

$A_i = \prod_j p_j^{r_{i,j}}$ と素因数分解する。ここで $p_j$ は素数で $r_{i,j} \geq 0$ である。

$e_{1, j}$ をすべての $A_i$ を素因数分解したときの $p_j$ の指数の最大値、$e_{2, j}$ を $p_j$ の指数の2番目に大きい値とする。

$ = \prod_j p_j^{e_{1,j}}$ であり、$A_i$ を使わないときの LCM は $r_{i,j}$ が $e_{1,j}$ と等しいときは $p_j$ の指数を $e_{2,j}$ に変え、$e_{1,j}$ のままでいいから、$A_i$ を使わないときの LCM は $\mathrm{LCM}(A_1, \cdots, A_N)$ の値に対して $r_{i,j} = e_{1,j}$ なら $p_j^{e_{1,j} - e_{2,j}}$ で割るということを全ての素因数に対して行えばよい。

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

    // ll M = (ll)1e7 + 1;
    // vll lpf(M);
    // iota(all(lpf), 0ll);
    // rep2(i, 2, M) {
    //     for (ll j = i + i; j < M; j += i) {
    //         if (lpf[j] > i)
    //             lpf[j] = i;
    //     }
    // }

    ll M = (ll)1e7 + 1;
    vll lpf(M, -1);
    vll primes;
    rep2(d, 2, M) {
        if (lpf[d] < 0) {
            lpf[d] = d;
            primes.push_back(d);
        }
        for (ll p : primes) {
            if (p * d > M || p > lpf[d]) break;
            lpf[p * d] = p;
        }
    }

    auto cal = [&]() -> void {
        ll N;
        cin >> N;
        vll A(N);
        rep(i, N) cin >> A[i];

        map<ll, ll> e1, e2;
        for (ll x : A) {
            while (x != 1) {
                ll p = lpf[x], cnt = 0;

                while (x % p == 0) {
                    cnt++;
                    x /= p;
                }

                if (cnt > e1[p]) {
                    e2[p] = e1[p];
                    e1[p] = cnt;
                } else if (cnt > e2[p]) {
                    e2[p] = cnt;
                }
            }
        }

        mint cm = 1;
        for (auto [p, cnt] : e1) {
            cm *= ((mint)p).pow(cnt);
        }

        vll ans;
        for (ll x : A) {
            mint mul = cm;
            while (x != 1) {
                ll p = lpf[x], cnt = 0;

                while (x % p == 0) {
                    cnt++;
                    x /= p;
                }

                if (cnt == e1[p]) {
                    mul /= (mint(p).pow(e1[p] - e2[p]));
                }
            }
            ans.push_back(mul.val());
        }
        print(ans);
    };

    int t;
    cin >> t;
    rep(i, t) cal();
}

pollard rho method での方法。線形篩の2倍くらいの実行時間だが通った。 pollard rho method は yosupo judge のコードを使った。

https://atcoder.jp/contests/abc445/submissions/73350937

using ull = unsigned long long;
template <class T>
using V = vector<T>;
template <class T>
using VV = V<V<T>>;

// bit op
int bsf(uint x) { return __builtin_ctz(x); }
int bsf(ull x) { return __builtin_ctzll(x); }

// binary gcd
ll gcd(ll _a, ll _b) {
    ull a = abs(_a), b = abs(_b);
    if (a == 0) return b;
    if (b == 0) return a;
    int shift = bsf(a | b);
    a >>= bsf(a);
    do {
        b >>= bsf(b);
        if (a > b) swap(a, b);
        b -= a;
    } while (b);
    return (a << shift);
}

template <class T, class U>
T pow_mod(T x, U n, T md) {
    T r = 1 % md;
    x %= md;
    while (n) {
        if (n & 1) r = (r * x) % md;
        x = (x * x) % md;
        n >>= 1;
    }
    return r;
}

bool is_prime(ll n) {
    if (n <= 1) return false;
    if (n == 2) return true;
    if (n % 2 == 0) return false;
    ll d = n - 1;
    while (d % 2 == 0) d /= 2;
    for (ll a : {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37}) {
        if (n <= a) break;
        ll t = d;
        ll y = pow_mod<__int128_t>(a, t, n);  // over
        while (t != n - 1 && y != 1 && y != n - 1) {
            y = __int128_t(y) * y % n;  // flow
            t <<= 1;
        }
        if (y != n - 1 && t % 2 == 0) {
            return false;
        }
    }
    return true;
}

ll pollard_single(ll n) {
    if (is_prime(n)) return n;
    if (n % 2 == 0) return 2;
    ll st = 0;
    auto f = [&](ll x) { return (__int128_t(x) * x + st) % n; };
    while (true) {
        st++;
        ll x = st, y = f(x);
        while (true) {
            ll p = gcd((y - x + n), n);
            if (p == 0 || p == n) break;
            if (p != 1) return p;
            x = f(x);
            y = f(f(y));
        }
    }
}

V<ll> pollard(ll n) {
    if (n == 1) return {};
    ll x = pollard_single(n);
    if (x == n) return {x};
    V<ll> le = pollard(x);
    V<ll> ri = pollard(n / x);
    le.insert(le.end(), ri.begin(), ri.end());
    return le;
}

vector<pair<ll, ll>> factorize(ll n) {
    vll ps = pollard(n);
    map<ll, ll> mp;
    for (ll x : ps) mp[x]++;

    vector<pair<ll, ll>> facs;
    for (auto [k, cnt] : mp) facs.push_back({k, cnt});
    return facs;
}

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

    auto cal = [&]() -> void {
        ll N;
        cin >> N;
        vll A(N);
        rep(i, N) cin >> A[i];

        vector<vector<pair<ll, ll>>> facs;
        for (ll a : A) {
            facs.push_back(factorize(a));
        }

        map<ll, ll> e1, e2;
        rep(i, N) {
            for (auto [p, cnt] : facs[i]) {
                if (e1[p] < cnt) {
                    e2[p] = e1[p];
                    e1[p] = cnt;
                } else if (e2[p] < cnt) {
                    e2[p] = cnt;
                }
            }
        }

        mint cm = 1;
        for (auto [p, cnt] : e1) {
            cm *= ((mint)p).pow(cnt);
        }

        vll ans;
        rep(i, N) {
            mint v = cm;
            for (auto [p, cnt] : facs[i]) {
                if (e1[p] == cnt) {
                    v /= mint(p).pow(e1[p] - e2[p]);
                }
            }
            ans.push_back(v.val());
        }
        print(ans);
    };

    int t;
    cin >> t;
    rep(i, t) cal();
}

F. Exactly K Steps 2

https://atcoder.jp/contests/abc445/tasks/abc445_f

2026/2/15 自力 AC

ダブリングで解く。

$D(d, i, j)$ を $j$ から出発して $2^d$ 回の操作後に $i$ に到達するときの最小コストとすると、 $D(d, i, j) = \min_k \\\{ D(d-1, i, k) + D(d-1, k, j) \\\}$ である。$0$ 回の操作のときの初期値は対角成分が 0、それ以外は $\infty$ とする。

これより $K$ 回の操作後の最小コストを求めて、対角成分について出力すれば良い。

struct Cost {
    ll N;
    vvll data;

    Cost(ll N) : N(N) {
        data = vvll(N, vll(N, INF));
        rep(i, N) data[i][i] = 0;
    }

    Cost operator*(const Cost& other) {
        vvll vals(N, vll(N, INF));

        rep(k, N) rep(i, N) rep(j, N) {
            chmin(vals[i][j], this->data[i][k] + other.data[k][j]);
        }

        Cost ret(N);
        ret.data = vals;
        return ret;
    }
};

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

    ll N, K;
    cin >> N >> K;
    vvll C(N, vll(N));
    rep(i, N) rep(j, N) cin >> C[i][j];

    ll M = 31;

    // powcost[d][i][j]: j から出発して 2^d の操作後に i に到達するときの最小コスト
    vector powcost(M, Cost(N));
    powcost[0].data = C;
    rep2(d, 1, M) {
        powcost[d] = powcost[d - 1] * powcost[d - 1];
    }

    Cost now(N);
    rep(i, M) {
        if (K >> i & 1) {
            now = powcost[i] * now;
        }
    }

    vll ans;
    rep(i, N) {
        cout << now.data[i][i] << '\n';
    }
}

G. Knight Placement

https://atcoder.jp/contests/abc445/tasks/abc445_g

ABC 445

Table of Contents

A. Strong Word

B. Center Alignment

C. Sugoroku Destination

D. Reconstruct Chocolate

E. Many LCMs

F. Exactly K Steps 2

G. Knight Placement