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

    좋은 웹페이지 즐겨찾기