ARC 164

Fri, May 2, 2025

A. Ternary Decomposition

https://atcoder.jp/contests/arc164/tasks/arc164_a

自力 AC.

$N$ を3進数で表現したとき、すなわち $N = \sum_{i=0}^m c_i 3^i$ と展開したとき $\sum_i c_i$ が $N$ を 3 の冪乗のみで構成したときの項の個数の最小値である。

ここで $n > 0$ のとき $3^n = 3^{n-1} + 3^{n-1} + 3^{n-1}$ とできるので1項を3項に分解できる。すなわち、1つの項を分解すると項数は $+2$ される。

現時点での項数を $S$ とする。 $3^n$ を $x$ を分解すると $2x$ 個項数が増えるので、分解すべき最大の個数は

\begin{align*} S + 2x &\leq K \\ x &\leq \frac{K - S}{2} \\ x &\leq \floor{\frac{K - S}{2}} \end{align*}

となる。

この操作を $3^n$ が大きい方から順に行い、最終的に個数が $K$ にすることができれば Yes、できなければ No と出力する。

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

    vll tp;
    {
        ll t = 1;
        while (t <= (ll)1e18) {
            tp.push_back(t);
            t *= 3;
        }

        reverse(all(tp));
    }

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

        int M = tp.size();
        ll T = N;
        vll cnt(M);
        rep(i, M) {
            ll q = T / tp[i];
            cnt[i] = q;
            T -= q * tp[i];
        }

        ll sum = accumulate(all(cnt), 0ll);
        rep(i, M - 1) {
            if (cnt[i] == 0) continue;
            if (sum <= K) {
                ll x = min(cnt[i], (K - sum) / 2);
                cnt[i] -= x;
                cnt[i + 1] += x * 3;
                sum += x * 2;
            }
        }

        yesno(sum == K);
    };

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

B. Switching Travel

https://atcoder.jp/contests/arc164/tasks/arc164_b

2日位かけて AC。

直線の移動では移動元の色と現在いる場所の色が一緒で戻ることはできないため、経路が存在するとすれば閉路を形成する必要がある。移動するたびに移動元の色が変わるため閉路の経路は以下の2通りのどちらかになる必要がある。

+--B-W-W-B--+       +--W-B-B-W--+
W           W       B           B
|           |       |           |
B           B       W           W
+----...----+       +----...----+

まず、色の異なる2点をつなぐ辺を全て連結させた後、同じ色の同士の頂点を結ぶ辺を加えたときに閉路になるかどうかを調べる。閉路が存在すれば Yes を出力し、存在しなければ No を出力する。

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

    int N, M;
    cin >> N >> M;

    vector<pair<int, int>> es;

    rep(i, M) {
        int a, b;
        cin >> a >> b;
        a--, b--;
        es.emplace_back(a, b);
    }

    vint col(N);
    rep(i, N) cin >> col[i];

    vector<pair<int, int>> same_col;

    dsu uf(N);
    for (auto [u, v] : es) {
        if (col[u] != col[v])
            uf.merge(u, v);
        else
            same_col.push_back({u, v});
    }

    int ok = 0;
    for (auto [u, v] : same_col) {
        if (uf.same(u, v))
            ok = 1;
    }
    yesno(ok);
}