Codeforces Round 865 (Div. 2) - E. Between (2200)

E. Between

관찰을 통해 풀 수 있었다.

대회는 아니지만 2200 자력솔은 최근 다시 코포 공부를 시작하고 처음하는듯하다.

Observation 1. 2 ~ n중 어떤 수가 a[i] 에 나오지 않는다면 길이는 무한하다.

1을 둔다음 그 수만 무한히 붙이면 되기 때문이다.

Observation 2

숫자 $x$가 수열에 나오는 횟수를 $f(x)$라고 하자. $f(1)=1$ 이다.

$b_i$ 라는 수가 $k$ 번 나오면, $a_i$는 최대 $k+1$ 번 나올 수 있다.

$1$ 이라는 수가 $1$ 번 나온다는 조건 덕에 우리는 BFS를 시행할 수 있다.

처음에 $2 \to n$ 의 수가 나올 수 있는 횟수를 $\infty$로 초기화하고 $f(1)=1$ 로만 해두고 BFS를 돌린다.

$b_i \to a_i$ 로의 모든 간선을 고려하여 $f(a_i)$ 가 $f(b_i)+1$ 보다 많이 나올 수 있다고 체크되어있을 때 $f(a_i) \coloneqq f(b_i)+1$ 해주고 $a_i$를 큐에 넣음으로 모든 수들의 $f$ 값을 구할 수 있다.

여기서 $f$ 값이 $\infty$인 수가 있다면 그 수를 무한히 붙여 수열을 만들 수 있다는 의미이므로 정답은 무한하다.

이제 모든 수의 $f$ 값을 가지고 정답을 어떻게 구성할 것인지가 문제이다.

내 Construction

fn(l, r) 을 $l \sim r$ 구간에서 숫자들을 채워넣는 재귀함수라고 하자.

남은 숫자들 중 가장 여러번 나와야 하는 수들의 집합 $S$ 를 고려한다.

$f(S_i)=1$ 이라면 그냥 모든 수를 $1 \to n$ 으로 훑으며 순서대로 $f(i) = 1$ 일 경우 넣어주고 끝낸다.

if (cnt[mxi] == 1) {  
   for (int i = l, j = 1; i <= r; i++) {  
      while (!cnt[j])j++;  
      ans[i] = j;  
      cnt[j]--;  
   }  
   return;  
}

그렇지 않다면 $S$에 있는 수들은 나와야 할 횟수가 $2$ 이상인 것들이므로, $S=\{1,2,3\}$ 이라 한다면

$1,2,3,[\dots],1,2,3$ 처럼 구간을 채우고 중간 부분은 다시 재귀호출한다.

이 방법이 성립하는 이유는 다음과 같다.

$a_i, b_i$가 있다고 해보자.

일단 $1,2,3$ 중 $a_i$ 에 존재하는 것이 있다면 $b_i$ 가 무엇이여도 항상 그것들의 사이에 들어가게 분배된다.

자세히 설명은 못하겠는데, 에디토리얼도 대략 이런 방식으로 순서대로 끼워넣어서 만드는것같다.

void solve() {  
   int n, m;  
   cin >> n >> m;  
   vector<pi> p;  
   vi a_has(n + 1);  
   vvi ba(n + 1), ab(n + 1);  
   for (int i = 0; i < m; i++) {  
      int a, b;  
      cin >> a >> b;  
      if (a == 1) continue;  
      a_has[a] = 1;  
      p.pb({a, b});  
      ba[b].pb(a);  
      ab[a].pb(b);  
   }  
   for (int i = 1; i <= n; i++) sort(all(ab[i]));  
   m = sz(p);  
   if (n == 1) {  
      cout << "FINITE\n1\n1\n";  
      return;  
   }  
   vi possible(n + 1, 1e9);  
   possible[1] = 1;  
   queue<int> q;  
   q.push(1);  
   while (sz(q)) {  
      int b = q.front();  
      q.pop();  
  
      for (int a: ba[b]) {  
         if (possible[a] > possible[b] + 1) {  
            possible[a] = possible[b] + 1;  
            q.push(a);  
         }  
      }  
   }  
   debug(possible);  
   int sum = 1;  
   for (int i = 2; i <= n; i++) {  
      if (possible[i] == 1e9) {  
         cout << "INFINITE\n";  
         return;  
      }  
      sum += possible[i];  
   }  
   cout << "FINITE\n" << sum << '\n';  
   vi ans(sum + 1);  
   vi cnt = possible;  
   function<void(int, int)> fn = [&](int l, int r) -> void {  
      int mxi = 1, sum = 0;  
      for (int i = 1; i <= n; i++) {  
         sum += cnt[i];  
         if (cnt[i] > cnt[mxi]) mxi = i;  
      }  
      assert(r - l + 1 == sum);  
  
      if (cnt[mxi] == 1) {  
         for (int i = l, j = 1; i <= r; i++) {  
            while (!cnt[j])j++;  
            ans[i] = j;  
            cnt[j]--;  
         }  
         return;  
      }  
  
      vi mx_list;  
      for (int i = 1; i <= n; i++) {  
         if (cnt[i] == cnt[mxi]) mx_list.pb(i);  
      }  
      int L = sz(mx_list);  
  
      for (int i = l; i < l + L; i++) ans[i] = mx_list[i - l];  
      for (int i = r - L + 1; i <= r; i++) ans[i] = mx_list[i - (r - L + 1)];  
      for (int i: mx_list) cnt[i] -= 2;  
      fn(l + L, r - L);  
   };  
   fn(1, sum);  
   for (int i = 1; i <= sum; i++) cout << ans[i] << ' ';  
   cout << endl;  
}