第17回アルゴリズム実技検定 (PAST 017)

Wed, Apr 16, 2025

H - 履修登録

解説 AC.

dp[i][j] を $i$ 限目までの科目をこなして $j$ 単位取得するのに必要な最小の労力とする。

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

    ll n, m;
    cin >> n >> m;
    vll a(n), b(n), c(n);
    rep(i, n) cin >> a[i] >> b[i] >> c[i];

    vector<vector<pair<ll, ll>>> lec(5001);
    rep(i, n) {
        lec[b[i]].push_back({a[i], c[i]});
    }

    vvll dp(5001, vll(m + 1, INF));
    dp[0][0] = 0;
    rep2(i, 1, 5001) {
        rep(j, m + 1) {
            // i 限目の科目を取らない場合
            chmin(dp[i][j], dp[i - 1][j]);

            // i 限目の科目を取る場合
            rep(k, lec[i].size()) {
                chmin(dp[i][j], dp[i - 1][max(0ll, j - lec[i][k].second)] + lec[i][k].first);
            }
        }
    }

    ll ans = dp[5000][m];
    if (ans == INF)
        ans = -1;
    cout << ans << endl;
}

K - 正しいチェックディジット

https://atcoder.jp/contests/past17-open/tasks/past17_k

昔解けなくて挫折したっぽい。解説見ていたのかもしれないが全く覚えてないので解説見ずに自力で解けたということにする。

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

    int N;
    string S;
    cin >> N >> S;

    ll sum = 0;
    vint ids;
    rep(i, N) {
        if (S[i] == '?') {
            ids.push_back(i + 1);
            continue;
        }

        sum += (i + 1) * (S[i] - '0');
        sum %= 10;
    }

    int m = ids.size();

    if (m == 0 && sum != 0) {
        yesno(false);
        return;
    }

    vvint dp(m + 1, vint(10, 0));
    dp[0][sum] = 1;
    rep2(i, 1, m + 1) {
        rep(j, 10) {
            if (dp[i - 1][j] == 0)
                continue;
            rep(k, 10) {
                dp[i][(j + ids[i - 1] * k) % 10] = 1;
            }
        }
    }

    if (dp[m][0] == 0) {
        yesno(false);
        return;
    }

    vint ans;
    int now = 0;
    for (int i = m; i >= 1; i--) {
        rep(j, 10) {
            int t = 10 - (j * ids[i - 1]) % 10;
            t %= 10;
            int nx = (now + t) % 10;
            if (dp[i - 1][nx]) {
                ans.push_back(j);
                now = nx;
                break;
            }
        }
    }
    reverse(all(ans));
    yesno(true);

    int cnt = 0;
    rep(i, N) {
        if (S[i] == '?') {
            S[i] = '0' + ans[cnt++];
        }
    }
    cout << S << endl;
}

解説読んで組み直したバージョン

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

    int N;
    string S;
    cin >> N >> S;
    S = "_" + S;

    vvint dp(N + 1, vint(10, 0));
    dp[0][0] = 1;

    rep2(i, 1, N + 1) {
        rep(j, 10) {
            if (dp[i - 1][j] == 0)
                continue;
            if (S[i] != '?') {
                int k = S[i] - '0';
                dp[i][(j + i * k) % 10] = 1;
            } else {  // S[i] = '?'
                rep(k, 10) {
                    dp[i][(j + i * k) % 10] = 1;
                }
            }
        }
    }

    if (dp[N][0] == 0) {
        yesno(false);
        return;
    }

    vint ans;
    int now = 0;
    for (int i = N; i >= 1; i--) {
        if (S[i] == '?') {
            rep(j, 10) {
                int t = 10 - (j * i) % 10;
                t %= 10;

                int nx = (now + t) % 10;
                if (dp[i - 1][nx]) {
                    ans.push_back(j);
                    now = nx;
                    break;
                }
            }
        } else {
            int t = 10 - (S[i] - '0') * i % 10;
            t %= 10;
            int nx = (now + t) % 10;
            ans.push_back(S[i] - '0');
            now = nx;
        }
    }
    reverse(all(ans));
    rep(i, N) {
        if (S[i + 1] == '?') {
            S[i + 1] = '0' + ans[i];
        }
    }
    yesno(true);
    cout << S.substr(1, N) << endl;
}

L - 割引券

ワーシャルフロイド (warshall-floyd) で解く。

$dp_{i,j}$ を2点間の距離とする。割引券を使わない場合は普通に warshall-floyd を使って

for k = 1 to N
    for i = 1 to N
        for j = 1 to N
            dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])

を計算すればよい。

一方 $dp^\prime_{i,j}$ を $i$ から $j$ まで到達するまでに1回割引券を使ったときの距離とすると

for k = 1 to N
    for i = 1 to N
        for j = 1 to N
            dp'[i][j] = min(dp[i][j], dp'[i][k] + dp[k][j])
            dp'[i][j] = min(dp[i][j], dp[i][k] + dp'[k][j])

とすることで1回だけ割引券を使った場合の最短距離を求めることができる。割引券は常に使ったほうがお得なので $dp^\prime_{i,j}$ の値を出力すればよい。

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

    int N;
    cin >> N;
    vector A(N, vll(N, INF)), B(N, vll(N, INF));
    rep(i, N) {
        rep2(j, i + 1, N) {
            cin >> A[i][j];
            A[j][i] = A[i][j];
        }
    }
    rep(i, N) {
        rep2(j, i + 1, N) {
            cin >> B[i][j];
            B[j][i] = B[i][j];
        }
    }

    vector dp(2, vvll(N, vll(N)));
    rep(i, N) rep(j, N) {
        dp[0][i][j] = A[i][j];
        dp[1][i][j] = B[i][j];
    }

    rep(k, N) rep(i, N) rep(j, N) {
        chmin(dp[0][i][j], dp[0][i][k] + dp[0][k][j]);
        chmin(dp[1][i][j], dp[1][i][k] + dp[0][k][j]);
        chmin(dp[1][i][j], dp[0][i][k] + dp[1][k][j]);
    }

    rep(i, N) {
        rep2(j, i + 1, N) {
            if (j != i + 1)
                cout << ' ';
            cout << dp[1][i][j];
        }
        cout << endl;
    }
}

第17回 アルゴリズム実技検定 (PAST 017)

Table of Contents

H - 履修登録

K - 正しいチェックディジット

L - 割引券

第17回アルゴリズム実技検定 (PAST 017)