ABC 404

Sat, May 3, 2025

B - Grid Rotation

90度回転を 0 ~ 3 回行い、それぞれのときの色が違うマスの数 + 回転回数が答え。配列を90度回転させるところが一番難しい。

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

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

    auto rotr90 = [&](vector<string>& S) -> vector<string> {
        vector<string> newS = S;
        rep(i, N) {
            rep(j, N) {
                // newS[j][N - 1 - i] = S[i][j];
                newS[i][j] = S[N - j - 1][i];
            }
        }
        return newS;
    };

    ll ans = INF;
    rep(k, 4) {
        if (k)
            S = rotr90(S);
        ll cnt = k;
        rep(i, N) rep(j, N) {
            if (S[i][j] != T[i][j])
                cnt++;
        }
        chmin(ans, cnt);
    }
    cout << ans << endl;
}

C - Cycle Graph?

union find で実装しようとして2ペナを食らった。union find で実装する場合は連結であることと、全てのノードの次数が2であることを確認する必要があった。コンテスト中は union find 解法が思いつかなかったので dfs で実装した。

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

    ll N, M;
    cin >> N >> M;

    if (M != N) {
        yesno(false);
        return;
    }

    vvint graph(N);
    rep(i, M) {
        int u, v;
        cin >> u >> v;
        u--, v--;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }

    vint used(N);

    auto dfs = [&](auto dfs, int now, int p, int depth) -> bool {
        if (now == 0 && depth == N)
            return true;

        for (int nx : graph[now]) {
            if (nx == p)
                continue;
            if (used[nx])
                continue;
            used[nx] = 1;
            if (dfs(dfs, nx, now, depth + 1))
                return true;
        }
        return false;
    };

    yesno(dfs(dfs, 0, -1, 0));
}

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

    ll N, M;
    cin >> N >> M;

    if (M != N) {
        yesno(false);
        return;
    }

    vector<pair<int, int>> es;

    vvint graph(N);
    rep(i, M) {
        int u, v;
        cin >> u >> v;
        u--, v--;
        es.emplace_back(u, v);
        graph[u].push_back(v);
        graph[v].push_back(u);
    }

    int ok = 1;
    rep(i, N) if (graph[i].size() != 2) ok = 0;
    if (!ok) {
        yesno(false);
        return;
    }

    dsu uf(N);

    for (auto [u, v] : es) {
        if (uf.same(u, v)) {
            uf.merge(u, v);
            // 連結かチェック
            yesno(uf.size(u) == N);
            return;
        }
        uf.merge(u, v);
    }
    yesno(false);
}

D - Goin’ to the Zoo

同じ動物は2回見れば十分なので一つの動物園に行く回数は最大で2回である。

動物園毎にどの動物が見れるかを記録しておき、訪れる動物園の組み合わせを bit 全探索した。 $2^{2N}$ で bit 全探索して $i \equiv j \mod N$ なる $j$ bit 目が立っていた場合は動物園 $i$ に訪れたとして計算した。 $N = 10$ のとき $2^{20} = 1048576$ 通りの組み合わせの全探索なので十分間に合うが、動物園 $i$ に1度しか訪れないケースをダブルカウントしているので無駄が多い。

$3^N$ 通りで全探索して動物園 $i$ を訪れる回数を $0, 1, 2$ 回で表現したほうが良かった。

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

    ll N, M;
    cin >> N >> M;

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

    // animals[i]: 動物園 i で見ることのできる動物
    vvint animals(N);

    rep(i, M) {
        int k;
        cin >> k;
        rep(j, k) {
            int a;
            cin >> a;
            a--;
            animals[a].push_back(i);
        }
    }

    ll ans = INF;
    rep(i, 1 << (N * 2)) {
        vll watch(M);
        ll tmpcost = 0;
        rep(j, N * 2) {
            if ((i >> j) & 1) {
                tmpcost += costs[j % N];
                for (int x : animals[j % N])
                    watch[x]++;
            }
        }
        int ok = 1;
        for (int cnt : watch) {
            if (cnt < 2)
                ok = 0;
        }
        if (ok)
            chmin(ans, tmpcost);
    }
    cout << ans << endl;
}

$3^N$ loop 版

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, M;
    cin >> N >> M;

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

    // animals[i]: 動物園 i で見ることのできる動物
    vvint animals(N);

    rep(i, M) {
        int k;
        cin >> k;
        rep(j, k) {
            int a;
            cin >> a;
            a--;
            animals[a].push_back(i);
        }
    }

    ll ans = INF;
    rep(i, intpow(3, N)) {
        ll t = i;
        vint watch(M);
        ll sum = 0;
        rep(j, N) {
            int cnt = t % 3;
            t /= 3;
            sum += costs[j] * cnt;
            rep(k, cnt) {
                for (int x : animals[j])
                    watch[x]++;
            }
        }

        int ok = 1;
        for (int x : watch) {
            if (x < 2)
                ok = 0;
        }

        if (ok)
            chmin(ans, sum);
    }
    cout << ans << endl;
}

E - Bowls and Beans

解説 AC.

豆が入っている一番後ろの茶碗から順に豆を前に移動させていく。

茶碗 $i$ から $k$ 回の移動で他の豆が入っている茶碗に到達できるのであればその茶碗に移動させるということを繰り返す。必要な移動の合計が答え。 sentinel として茶碗 0 には豆を入れておくと実装が楽。

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

    ll N;
    cin >> N;
    vll C(N), A(N);
    rep2(i, 1, N) cin >> C[i];
    rep2(i, 1, N) cin >> A[i];

    vint bean_id;
    rep(i, N) {
        if (A[i])
            bean_id.push_back(i);
    }
    reverse(all(bean_id));
    A[0] = 1;

    ll ans = 0;
    for (int x : bean_id) {
        ll l = x - C[x], r = x;
        ll cnt = 0;
        while (true) {
            cnt++;
            ll tmpl = l;
            int ok = 0;
            rep2(i, l, r) {
                chmin(tmpl, i - C[i]);
                if (A[i]) {
                    ok = 1;
                }
            }
            if (ok) {
                ans += cnt;
                break;
            }
            r = l;
            l = tmpl;
        }
    }
    cout << ans << endl;
}

ABC 404

Table of Contents

B - Grid Rotation

C - Cycle Graph?

D - Goin’ to the Zoo

E - Bowls and Beans