第19回アルゴリズム実技検定 (PAST 019)

Sun, Mar 30, 2025

C - 良さそうな数 / Goodish or Not

DP で解いたが、解説読んで普通に桁を変えるのを全探索すればいいだけだった

DP で解く場合は dp[i][j] を左から $i$ 桁目を $j$ にしたときのそれまで変更回数の最小値とする。

// DP 解放
void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    string S;
    cin >> S;

    int n = S.size();
    if (n == 1) {
        yesno(true);
        return;
    }

    vint v(n);
    rep(i, n) {
        v[i] = S[i] - '0';
    }

    vvint dp(n + 1, vint(10, INF));
    rep2(i, 1, 10) {
        if (v[0] != i)
            dp[0][i] = 1;
        else
            dp[0][i] = 0;
    }

    rep2(i, 1, n) {
        rep(j, 10) {
            int change = v[i] != j;
            if (j - 1 >= 0) {
                chmin(dp[i][j], dp[i - 1][j - 1] + change);
            }
            if (j + 1 <= 9) {
                chmin(dp[i][j], dp[i - 1][j + 1] + change);
            }
            chmin(dp[i][j], dp[i - 1][j] + change);
        }
    }

    int ok = 0;
    rep(i, 10) {
        if (dp[n - 1][i] <= 1)
            ok = 1;
    }
    yesno(ok);
}

// 全探索解法
void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    string S;
    cin >> S;

    int n = S.size();

    vint v(n);
    rep(i, n) {
        v[i] = S[i] - '0';
    }

    auto check = [](vint& v) -> bool {
        bool ok = true;
        int n = v.size();
        if (n == 1)
            return true;

        if (v[0] == 0)
            return false;

        rep(i, n - 1) {
            if (abs(v[i] - v[i + 1]) > 1)
                ok = false;
        }

        return ok;
    };

    rep(i, n) {
        vint t = v;
        rep(j, 10) {
            t[i] = j;
            if (check(t)) {
                yesno(true);
                return;
            }
        }
    }

    yesno(false);
}

K - 隣接禁止

木 DP の問題

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

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

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

    // dp[i][j][k]:
    // i: node 番号
    // j: node i を使うかどうか
    // k: k 個の頂点を選んだときの総和の最大値
    vector<vvll> dp(N, vvll(2, vll(K + 1, -INF)));

    auto dfs = [&](auto dfs, int now, int p) -> void {
        for (int nx : graph[now]) {
            if (nx == p)
                continue;
            dfs(dfs, nx, now);
        }

        dp[now][0][0] = 0;
        dp[now][1][1] = A[now];

        for (int nx : graph[now]) {
            if (nx == p)
                continue;
            {
                // now 使用
                vll tmp = dp[now][1];
                vll v = dp[nx][0];

                rep(i, K + 1) {
                    rep(j, K + 1) {
                        if (i + j <= K) {
                            if (dp[now][1][i] >= 0 && v[j] >= 0)
                                chmax(tmp[i + j], dp[now][1][i] + v[j]);
                        }
                    }
                }
                dp[now][1] = tmp;
            }
            {
                // now 不使用
                vll tmp = dp[now][0];
                rep(i, K + 1) {
                    rep(j, K + 1) {
                        if (i + j <= K) {
                            if (dp[now][0][i] >= 0 && dp[nx][0][j] >= 0)
                                chmax(tmp[i + j], dp[now][0][i] + dp[nx][0][j]);
                            if (dp[now][0][i] >= 0 && dp[nx][1][j] >= 0)
                                chmax(tmp[i + j], dp[now][0][i] + dp[nx][1][j]);
                        }
                    }
                }
                dp[now][0] = tmp;
            }
        }
    };

    dfs(dfs, 0, -1);
    ll ans = max(dp[0][0][K], dp[0][1][K]);
    if (ans < 0)
        ans = -1;
    cout << ans << endl;
}

L - 最長のジグザグ

first try から数日経って自力 AC.

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

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

    auto check = [&](bool next_up) -> int {
        int ans = 1;
        int v = B[0];
        rep2(i, 1, N) {
            if (next_up && v < B[i]) {  // next up
                ans++;
                next_up = false;
            } else if (!next_up && v > B[i]) {  // next down
                ans++;
                next_up = true;
            }
            v = B[i];
        }
        return ans;
    };

    cout << max(check(true), check(false)) << '\n';
}

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

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

    bool next_up = true;
    rep2(i, 1, N) {
        if (B[0] != B[i]) {
            next_up = B[0] < B[i];
            break;
        }
    }

    int ans = 1;
    int v = B[0];
    rep2(i, 1, N) {
        if (next_up && v < B[i]) {  // next up
            ans++;
            next_up = false;
        }
        if (!next_up && v > B[i]) {  // next down
            ans++;
            next_up = true;
        }
        v = B[i];
    }

    cout << ans << '\n';
}

M - DAG ゲーム

ゴールからスタートに向かって進める。現在の score を $sc$ とすると、次のノードに行くときの score は $sc \times w + P[nx]$ となる。

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

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

    vector<vector<Edge>> graph(N);
    rep(i, M) {
        int u, v;
        double w;
        cin >> u >> v >> w;
        u--, v--;
        graph[v].push_back({u, w});
    }

    vector<double> score(N, 0.0);
    score[N - 1] = P.back();
    score[0] = -1;
    // cost, position
    priority_queue<tuple<double, int>> pq;

    // N-1 から 0 に向かって進める
    pq.push({P.back(), N - 1});
    while (pq.size()) {
        auto [sc, now] = pq.top();
        pq.pop();

        if (score[now] > sc)
            continue;
        for (auto [nx, w] : graph[now]) {
            double new_sc = sc * w + (double)P[nx];
            if (score[nx] >= new_sc)
                continue;
            score[nx] = new_sc;
            pq.push({new_sc, nx});
        }
    }

    double ans = score[0];
    if (score[0] < 0.0) {
        cout << -1 << endl;
        return;
    }
    printf("%.9lf\n", ans);
}

N - 有限べき級数

解説 AC.

解説読んで理解はしたが技巧的過ぎて思いつかん。

モノイド $(S, \cdot : S \times S \rightarrow S, e \in S)$ の対応

$S = \{ f | f(t) = A + Bt, t \in \mathbb{R}, A \in \mathbb{R}, B \in \mathbb{R} \}$
$\cdot = \circ$ (関数の合成)
$e(t) = 0 + 1 \times t$

$f(t) = A + Bt$, $g(t) = C + Dt$ とするとき \begin{align*} (f \circ g)(t) &= f(g(t)) \\ &= f(C + Dt) \\ &= A + B(C+Dt) \\ &= A + BC + BDt \end{align*}

類題？ https://atcoder.jp/contests/arc008/tasks/arc008_4

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

    int N;
    cin >> N;
    vll A(N);
    rep(i, N) cin >> A[i];
    double x;
    cin >> x;

    using P = pair<double, double>;
    auto op = [](P l, P r) -> P {
        return {l.first + l.second * r.first, l.second * r.second};
    };
    auto e = []() -> P {
        return {0, 1};
    };

    segtree<P, op, e> seg(N);
    rep(i, N) {
        seg.set(i, {A[i], x});
    }

    int Q;
    cin >> Q;
    rep(i, Q) {
        int l, r;
        cin >> l >> r;
        l--, r--;
        printf("%.9lf\n", seg.prod(l, r + 1).first);
    }
}

O - 15パズル

解説 AC. ほぼ解けていたが答えが 30 を超えたときに -1 にするのを忘れていた。

双方向ダイクストラのようにスタートとゴールから動かして解く。スタートから 15 移動、ゴールから 15 移動して分を計算して、共通する配置のうち移動回数が最小となるものを出力。共通部分がなかった場合は -1 を出力。

空きマスの動かし方は始め 4 方向(隅以外の場合)に移動できて、そのあと来た方向異なる3方向に動かすから 15 回の移動での配置方法は高々 $4\times 3^{14} \leq 2 \times 10^7$ 通りなので実行時間に間にあう

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

    int n = 4;
    vector S(n, vint(n)), T(n, vint(n));
    rep(i, n) rep(j, n) cin >> S[i][j];
    rep(i, n) rep(j, n) cin >> T[i][j];

    map<vvint, int> dists, dists2;
    dists[S] = 0;
    dists2[T] = 0;

    auto cal = [&](vvint& M, map<vvint, int>& D) -> void {
        vint di = {0, 1, 0, -1};
        vint dj = {1, 0, -1, 0};
        queue<tuple<int, vvint, int, int>> que;
        rep(i, n) rep(j, n) {
            if (M[i][j] == -1)
                que.push({0, M, i, j});
        }

        while (que.size()) {
            auto [dist, X, i, j] = que.front();
            que.pop();

            rep(d, 4) {
                int ni = i + di[d], nj = j + dj[d];
                if (clamp(ni, 0, n - 1) != ni || clamp(nj, 0, n - 1) != nj)
                    continue;

                swap(X[i][j], X[ni][nj]);
                if (!D.count(X)) {
                    D[X] = dist + 1;
                    if (dist + 1 <= 15)
                        que.push({dist + 1, X, ni, nj});
                }
                swap(X[i][j], X[ni][nj]);
            }
        }
    };

    cal(S, dists);
    cal(T, dists2);

    int ans = INF;
    for (auto [v, cnt] : dists) {
        int x;
        if (dists2.count(v) && (x = dists2[v] + cnt) <= 30) {
            chmin(ans, x);
        }
    }
    if (ans == INF)
        ans = -1;
    cout << ans << endl;
}

第19回 アルゴリズム実技検定 (PAST 019)

Table of Contents