AtCoder ABC 160 D - Line++ (緑色, 400 点)

すごく色んな考え方ができる問題ですね！

問題へのリンク

問題概要

個の頂点を持つ無向グラフ がある。 の辺集合は

• と とを結ぶ辺
• 頂点 と頂点 とを結ぶ辺

とで構成されている。各 に対して、最短距離が であるような頂点対が何個あるかを求めよ。

制約

• 

考えたこと

めっちゃくちゃ色んな考え方ができる問題！！！
これ、実は制約が小さいので、とにかくなんとかして全頂点間の距離が求められれば OK！！！！！

解法 (1)： 何も考えずに BFS

をかけていいので、何も考えずに

• 全頂点を始点として
• BFS

というのができる。グラフの辺の本数は 本なので、1 回の BFS は で、全体でも になる。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int N, X, Y;
    cin >> N >> X >> Y;
    --X, --Y;
    vector<vector<int>> dist(N, vector<int>(N, -1));
    for (int s = 0; s < N; ++s) {
        queue<int> que;
        que.push(s);
        dist[s][s] = 0;
        while (!que.empty()) {
            auto v = que.front(); que.pop();
            vector<int> nvs;
            if (v > 0) nvs.push_back(v-1);
            if (v < N-1) nvs.push_back(v+1);
            if (v == X) nvs.push_back(Y);
            if (v == Y) nvs.push_back(X);
            for (auto nv : nvs) {
                if (dist[s][nv] == -1) {
                    dist[s][nv] = dist[s][v] + 1;
                    que.push(nv);
                }
            }
        }
    }
    vector<int> res(N, 0);
    for (int i = 0; i < N; ++i) {
        for (int j = i + 1; j < N; ++j) res[dist[i][j]]++;
    }
    for (int d = 1; d < N; ++d) cout << res[d] << endl;
}

解法 (2)： アドホックに求める

グラフの構造が特殊なことから、もう少しアドホックに求めることもできる。二頂点 i, j の最短距離は

• 辺 (X, Y) を使わない場合： abs(i - j)
• 頂点 i と頂点 X、頂点 j と頂点 Y とが結ばれる場合： abs(i - X) + abs(j - Y) + abs(X - Y)
• 頂点 i と頂点 Y、頂点 j と頂点 X とが結ばれる場合： abs(i - Y) + abs(j - X) + abs(X - Y)

これらの最小値が最短距離となる。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int N, X, Y;
    cin >> N >> X >> Y;
    --X, --Y;
    vector<int> res(N, 0);
    for (int i = 0; i < N; ++i) {
        for (int j = i + 1; j < N; ++j) {
            int d = min({abs(i-j), 
            abs(i-X)+abs(j-Y)+1, abs(i-Y)+abs(j-X)+1});
            res[d]++;
        }
    }
    for (int d = 1; d < N; ++d) cout << res[d] << endl;
}

解法 (3)： 「辺の追加」は O(N²) でできる

「全頂点間の最短距離」を求める問題、辺 (X, Y) がなければものすごく簡単で、

• dist[ i ][ j ] = abs(i - j)

となる。そして一般に、「辺を追加したときに全頂点間最短距離がどうなるか」は、 で求めることができる。具体的には、以下のようにすれば OK。

• 頂点 i から頂点 X へ行って、辺 (X, Y) を通って、頂点 Y から頂点 j へ行く場合

chmin(dp[ i ][ j ], dp[ i ][ X ] + dp[ X ][ j ] + 1)

• 頂点 i から頂点 Y へ行って、辺 (Y, X) を通って、頂点 X から頂点 j へ行く場合

chmin(dp[ i ][ j ], dp[ i ][ Y ] + dp[ Y ][ j ] + 1)

#include <bits/stdc++.h>
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

int main() {
    int N, X, Y;
    cin >> N >> X >> Y;
    --X, --Y;
    vector<int> res(N, 0);
    vector<vector<int>> dp(N, vector<int>(N));
    for (int i = 0; i < N; ++i) for (int j = 0; j < N; ++j) dp[i][j] = abs(i-j);
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            chmin(dp[i][j], dp[i][X] + dp[Y][j] + 1);
            chmin(dp[i][j], dp[i][Y] + dp[X][j] + 1);
        }
    }
    for (int i = 0; i < N; ++i) for (int j = i+1; j < N; ++j) res[dp[i][j]]++;
    for (int d = 1; d < N; ++d) cout << res[d] << endl;
}