ABC 160 | D - Line++

問題

https://atcoder.jp/contests/abc160/tasks/abc160_d

考えたこと

各頂点ごとにBFSでそれぞれの頂点に対する経路長を出し、各頂点以降の頂点の経路長の数を足し合わせればいい。
辺が少ないので$O(n^2)$で計算でき間に合う。

コード

実装時のTips

• 0-indexedに変換して計算する

#include <bits/stdc++.h>

#include <atcoder/all>

using namespace std;
using namespace atcoder;
using ll = long long;
using ld = long double;
using uint = unsigned int;
using ull = unsigned long long;
const int MOD = 1e9 + 7;

// sから各頂点までの距離を出す
vector<int> bfs(int n, vector<unordered_set<int>> &paths, int s) {
  const int inf = 1e9;
  vector<int> dist(n, inf);
  queue<tuple<int, int>> q;  // {頂点, 距離}
  q.push({s, 0});
  while (!q.empty()) {
    auto [i, d] = q.front();
    q.pop();
    if (dist[i] != inf) continue;
    dist[i] = d;
    for (auto nxt : paths[i]) {
      if (dist[nxt] != inf) continue;
      q.push({nxt, d + 1});
    }
  }

  return dist;
}

int main() {
  ll n, x, y;
  cin >> n >> x >> y;
  x--;
  y--;
  vector<unordered_set<int>> paths(n + 1);
  for (int i = 0; i < n - 1; i++) {
    paths[i].insert(i + 1);
    paths[i + 1].insert(i);
  }
  paths[x].insert(y);
  paths[y].insert(x);
  vector<int> k(n + 1);
  for (int i = 0; i < n; i++) {
    auto r = bfs(n, paths, i);
    for (int j = i + 1; j < r.size(); j++) {
      k[r[j]]++;
    }
  }
  for (int i = 1; i < n; i++) {
    cout << k[i] << endl;
  }
}

別解

解いた後に解説みたらもっと簡単にやり方があり確かになとなった。

$x$と$y$の経路を足す前なら頂点$i$と$j$の距離は$|i-j|$で求められる。

$x$と$y$を辺として足した場合、以下のように赤の経路の$|i-x| + 1 + |y - j|$が最短経路として更新される可能性がある。
これは$i$が$x$の前後にあろうと$j$が$y$の前後にあろうと計算式はかわらない。

よってコードは非常にシンプルになり以下のようになる。

#include <bits/stdc++.h>

#include <atcoder/all>

using namespace std;
using namespace atcoder;
using ll = long long;
using ld = long double;
using uint = unsigned int;
using ull = unsigned long long;
const int MOD = 1e9 + 7;

int main() {
  int n, x, y;
  cin >> n >> x >> y;
  x--;
  y--;
  vector<int> k(n);
  for (int i = 0; i < n; i++) {
    for (int j = i + 1; j < n; j++) {
      int v = min(abs(i - j), abs(i - x) + 1 + abs(y - j));
      k[v]++;
    }
  }
  for (int i = 1; i < n; i++) {
    cout << k[i] << endl;
  }
}

参考

https://atcoder.jp/contests/abc160/tasks/abc160_d/editorial