[AtCoder] ABC 160 D – Line++

2020年4月1日2020年12月15日

問題

方針

頂点 \( i \) と 頂点 \( j \) の最短距離を \( l(i, j) \ (i < j)\) とすると、頂点 \( X \) と 頂点 \( Y \) と経由して行く方法を考えると、

\[l(i, j) = \min(j – i , |X – i| + |Y – j| + 1)\]

となります。よって、全ての頂点間を調べることで解答できます。

コード

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

int main() {
    int N, X, Y;
    cin >> N >> X >> Y;
    ll cnt[N]{};
    // i < j
    for (int i = 1; i <= N; i++) {
        for (int j = i + 1; j <= N; j++) {
            int i_j = j - i;
            int i_X_Y_j = abs(X - i) + 1 + abs(Y - j);
            cnt[min(i_j, i_X_Y_j)]++;
        }
    }
    for (int i = 1; i < N; i++) {
        cout << cnt[i] << "\n";
    }
    return 0;
}