特定の操作で各都市から訪問できる都市の数を数えるC++プログラム

問題の概要

N個の座標点Pが (xi, yi) の形式で与えられているとします。ここで、xとyの値はそれぞれ1からNまでの自然数の順列になっています。

1からNまでの各kについて、自分は今「都市k」にいるものと考えます。次の操作を任意の回数だけ繰り返し実行できます。

操作： 現在いる都市と比較して、「x座標とy座標の両方が小さい都市」または「x座標とy座標の両方が大きい都市」へ移動する。

このとき、都市kから到達できる都市の総数を求めるのが目的です。

例えば、入力が P = [[1, 4], [2, 3], [3, 1], [4, 2]] の場合、出力は [1, 1, 2, 2] となります。

解き方のアプローチ

この問題を解くために、以下の手順に従います。

• x座標を基準にすべての都市をソートします。
• 先頭から順に都市を見ていきながら、それまでに処理した都市の中での最小のy座標（y_min）を追跡します。
• y_min + i が n と等しくなった時点で、それまでに集めた都市のグループは外部のどの都市にも移動できない「閉じたグループ（連結成分）」になります。これは、残りの都市がすべて現在のグループより小さなy座標を持つためです。
• 閉じたグループが確定したら、グループ内の全都市の答えをグループのサイズとして記録し、集合をクリアします。

n := size of P
Define one 2D array lst
for initialize i := 0, when i < n, update (increase i by 1), do:
   v := { P[i, 0], P[i, 1], i }
   insert v at the end of lst
sort the array lst
y_min := 1e9
Define one set se
Define an array ans of size n and fill with 0
for initialize i := 0, when i < n, update (increase i by 1), do:
   y_min := minimum of y_min and lst[i, 1]
   insert lst[i, 2] into se
   if y_min + i is same as n, then:
      for each element j in se
         ans[j] := size of se
      clear the set se
   if i is same as n - 1, then:
      for each element j in se
         ans[j] := size of se
for initialize i := 0, when i < n, update (increase i by 1), do:
   display ans[i]

C++による実装例

理解を深めるために、以下の実装例を見てみましょう。

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

void solve(vector<vector<int>> P){
   int n = P.size();
   vector<vector<int>> lst;
   for (int i = 0; i < n; i++){
      vector<int> v = { P[i][0], P[i][1], i };
      lst.push_back(v);
   }
   sort(lst.begin(), lst.end());
   int y_min = 1e9;
   set<int> se;
   vector<int> ans(n, 0);
   for (int i = 0; i < n; i++){
      y_min = min(y_min, lst[i][1]);
      se.insert(lst[i][2]);
      if (y_min + i == n){
         for (auto j : se)
            ans[j] = se.size();
         se.clear();
      }
      if (i == n - 1){
         for (auto j : se)
            ans[j] = se.size();
      }
   }
   for (int i = 0; i < n; i++){
      cout << ans[i] << ", ";
   }
}
int main(){
   vector<vector<int>> P = { { 1, 4 }, { 2, 3 }, { 3, 1 }, { 4, 2 } };
   solve(P);
}

入力

{ { 1, 4 }, { 2, 3 }, { 3, 1 }, { 4, 2 } }

出力

1, 1, 2, 2,