E. Between

관찰을 통해 풀 수 있었다.

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

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

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

Observation 2

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

bib_i 라는 수가 kk 번 나오면, aia_i는 최대 k+1k+1 번 나올 수 있다.

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

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

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

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

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

내 ConstructionPermalink

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

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

f(Si)=1f(S_i)=1 이라면 그냥 모든 수를 1→n1 \to n 으로 훑으며 순서대로 f(i)=1f(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;  
}

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

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

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

ai,bia_i, b_i가 있다고 해보자.

일단 1,2,31,2,3 중 aia_i 에 존재하는 것이 있다면 bib_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;  
}

Comments

You may also enjoy