Codeforces Round 868 (Div. 2)

A. A-characteristic (800)Permalink

A. A-characteristic

모든 $1, -1$은 붙어있어도 상관없다.

$n$개가 있다면 $1$이 $k$개가 있고 $-1$이 $n-k$개가 있는데, 그럼 총 쌍의 개수는

$\dbinom {k}{2} \cdot \dbinom {n-k}{2}$ 이다.

가능한 $k$를 $k \coloneqq 0 \to n$ 까지 순회해주며 $K$개가 나오는지 확인해주면 된다.

B. Sort with Step (900)Permalink

B. Sort with Step

$\lvert i-j \rvert=k$ 인 것만 swap이 가능하다는 것은 수열을 $k$개의 그룹으로 나눌 수 있다는 의미이다.

$i$번 째 있는 그룹엔 $i, i+k, i+2k, \dots$ 의 수들만 있어야 하며 자기가 들어가야 할 그룹에 있지 않은 수들의 개수를 bad count라고 하자.

이것이 $0$개라면 정답은 $0$이고, $2$개라면 정답은 $1$이고 아니라면 $-1$이다.

C. Strongly Composite (1300)Permalink

C. Strongly Composite

일단 $a$의 모든 수들을 소인수분해하자. $n \le 1,000$ 이라서 괜찮다.

이제 모든 소수들만 모아두자.

최대한 그룹의 크기를 최대로 만들어야 하므로 소수들을 어떻게 묶어야 할지 보자.

소수 $p$가 $k$개 있다고 하자.

$\{p, p\}$ 인 그룹은 가능하다. 왜냐하면 $p^2$ 의 합성수는 $p^2$ 밖에 없고 소수 $1$개, 합성수 $1$개로 소수가 더 적은 Strongly Composite 수이기 때문이다.

이렇게 모든 같은 소수들에서 두 개씩 뽑아내면 각 소수마다 $0 \text{~or~} 1$ 개의 소수들이 남고, 이 것들 개수의 합을 $K$라고 하자.

이제 서로 다른 소수들은 최소 $3$개씩 묶어야 한다. 따라서 정답에 $\left\lfloor \dfrac K3 \right\rfloor$ 을 더해준다.

D. Unique Palindromes (1900)Permalink

D. Unique Palindromes

$p \le 20$ 임을 보자.

이건 시간복잡도와 관련있을 수도 있지만, 알파벳은 최대 $26$개이므로 뭔가 이것과 연관지어 생각하는 것이 문제를 해결할 열쇠이다.

$c_i > n$ 이라면 불가능하다. 왜냐면 하나의 알파벳을 추가할 때 팰린드롬은 최대 $1$개씩 추가되기 때문이다.

같은 이유로 $x_{i+1}-x_i < c_{i+1}-c_i$ 라면 불가능하다. 추가할 수 있는 문자보다 늘어나야할 양이 많다면 불가능하다.

그리고 $c_i < 3$ 이라면 불가능하다. 처음 세 개는 무조건 팰린드롬이 $1$개 씩 늘어나게 추가할 수 밖에 없기 때문이다.

$3 < c_i \le n$ 이라고 하자.

문제를 푸는 핵심은 어떤 같은 문자를 계속 추가하면 항상 팰린드롬을 1 늘릴 수 있다는 것이다.

따라서 이렇게 길이를 늘릴 때 사용할 문자를 $0 \sim p-1$ 마다 $d$ 부터 시작해서 $d,e,f,g,\dots$ 처럼 늘려간다.

이제 $abc$는 어디다 사용할 것이냐면 팰린드롬을 늘리지 않게 하는 용도로 사용한다.

처음에 정답을 $abc$로 두고 만약 그 다음 $x_i=7,~c_i=5$ 라고 하자.

문자 $4$개를 추가해야되는데 팰린드롬은 $2$개만(현재 $3$개 이므로) 늘려야 하는 상황이다.

그럼 $2$개를 팰린드롬이 추가되지 않게 사용해야 하므로 $abc$ 를 계속 돌린다.

이후 $d$ 를 $2$개 추가한다.

$abc \to abcab \to abcabdd$

이제 다음번엔 $abc$에선 $c$를 사용해주고 늘리는 용도론 $e$를 사용해주면 정답을 구성해 나갈 수 있다.

void solve() {
   int n, k;
   cin >> n >> k;
   vector<pi> a(k);
   for (int i = 0; i < k; i++) cin >> a[i].fi, a[i].fi--;
   for (int i = 0; i < k; i++) cin >> a[i].se;
   sort(all(a));
   string ans;
   char nxt_add_char = 'd';
   char nxt_skip_char = 'a';
   ans = "abc";
 
   for (int i = 0; i < k; i++) {
      int x = a[i].fi, c = a[i].se;
 
      if (x <= 2) {
         if (x + 1 != c) {
            cout << "NO\n";
            return;
         }
         continue;
      }
 
      int diff = x + 1 - sz(ans); // 5 - 3
      int add = i == 0 ? (c - 3) : (a[i].se - a[i - 1].se);
 
      if (add > diff) {
         cout << "NO\n";
         return;
      }
 
      int skip = diff - add;
 
      while (skip--) {
         ans += nxt_skip_char;
         nxt_skip_char = (nxt_skip_char - 'a' + 1) % 3 + 'a';
      }
      while (add--) {
         ans += nxt_add_char;
      }
      nxt_add_char++;
   }
   cout << "YES\n" << ans << endl;
}

E. Removing Graph (2500)Permalink

E. Removing Graph

F. Random Walk (2600)Permalink

F. Random Walk