ABC 286

Mon, Mar 24, 2025

https://atcoder.jp/contests/abc286

A. Range Swap

https://atcoder.jp/contests/abc286/tasks/abc286_a

B. Cat

https://atcoder.jp/contests/abc286/tasks/abc286_b

C. Rotate and Palindrome

https://atcoder.jp/contests/abc286/tasks/abc286_c

D. Money in Hand

https://atcoder.jp/contests/abc286/tasks/abc286_d

E. Souvenir

https://atcoder.jp/contests/abc286/tasks/abc286_e

ワーシャルフロイドで解く。距離が短い場合は価値も更新. 距離が同じ場合は価値を高い方に更新する。はじめわーシャルフロイドの添字の実行順があったことを忘れて WA したが、なぜか3回回したら AC した。まぐれと思ったが3回実行すると正しい答えが返ってくることは証明されているらしい。

https://qiita.com/tmaehara/items/f56be31bbb7a468a04ed

コード中の注意点として距離が大きいときの条件と同じときの条件をまとめて書いてはいけない

if (dist[i][j] > dist[i][k] + dist[k][j]) {
    dist[i][j] = dist[i][k] + dist[k][j];
    value[i][j] = value[i][k] + value[k][j] - prices[k];
}
if (dist[i][j] == dist[i][k] + dist[k][j]) {
    chmax(value[i][j], value[i][k] + value[k][j] - prices[k]);
}

if (dist[i][j] >= dist[i][k] + dist[k][j]) {
    dist[i][j] = dist[i][k] + dist[k][j];
    chmax(value[i][j], value[i][k] + value[k][j] - prices[k]);
}

NG 版で書くと距離が大きいときの価値の値を使ってしまうことがあるため WA する。

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

    int n;
    cin >> n;
    vll prices(n);
    rep(i, n) cin >> prices[i];

    vector<string> s(n);
    rep(i, n) cin >> s[i];

    vvll dist(n, vll(n, INF));
    rep(i, n) dist[i][i] = 0;
    vvll value(n, vll(n));
    rep(i, n) value[i][i] = prices[i];
    rep(i, n) {
        rep(j, n) {
            if (s[i][j] == 'Y') {
                dist[i][j] = 1;
                value[i][j] = prices[i] + prices[j];
            }
        }
    }

    rep(_, 3) {
        rep(i, n) {
            rep(j, n) {
                rep(k, n) {
                    if (dist[i][j] > dist[i][k] + dist[k][j]) {
                        dist[i][j] = dist[i][k] + dist[k][j];
                        value[i][j] = value[i][k] + value[k][j] - prices[k];
                    }
                    if (dist[i][j] == dist[i][k] + dist[k][j]) {
                        chmax(value[i][j], value[i][k] + value[k][j] - prices[k]);
                    }
                }
            }
        }
    }

    int q;
    cin >> q;
    rep(i, q) {
        int u, v;
        cin >> u >> v;
        u--, v--;
        if (dist[u][v] == INF)
            cout << "Impossible" << endl;
        else
            cout << dist[u][v] << ' ' << value[u][v] << endl;
    }
}

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

    int n;
    cin >> n;
    vll prices(n);
    rep(i, n) cin >> prices[i];

    vector<string> s(n);
    rep(i, n) cin >> s[i];

    vvll dist(n, vll(n, INF));
    rep(i, n) dist[i][i] = 0;
    vvll value(n, vll(n));
    rep(i, n) {
        rep(j, n) {
            if (s[i][j] == 'Y') {
                dist[i][j] = 1;
                value[i][j] = prices[i] + prices[j];
            }
        }
    }

    rep(k, n) {
        rep(i, n) {
            rep(j, n) {
                if (dist[i][j] > dist[i][k] + dist[k][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                    value[i][j] = value[i][k] + value[k][j] - prices[k];
                }
                if (dist[i][j] == dist[i][k] + dist[k][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                    chmax(value[i][j], value[i][k] + value[k][j] - prices[k]);
                }
            }
        }
    }

    int q;
    cin >> q;
    rep(i, q) {
        int u, v;
        cin >> u >> v;
        u--, v--;
        if (dist[u][v] == INF)
            cout << "Impossible" << endl;
        else
            cout << dist[u][v] << ' ' << value[u][v] << endl;
    }
}