Codeforces Round 877 (Div. 2)

Codeforces Round 877 (Div. 2)

---

오늘은 정말 ABCD 모두 아이디어가 특히 필요한 문제들만 모아둔 문제들의 집합이였다.

D를 극적으로 풀어서 오렌지 퍼포를 낼 뻔했으나 2090 정도로 나왔다.

계속 블루 퍼포 왔다리 갔다리 하다가 그냥 최근 며칠 코포 문제들만 열심히 풀다보니 그래도 성취가 있는것같다.

업솔빙은 내일 에디토리얼 보면서 하자.

A. Blackboard List

A. Blackboard List

$\text{Min}(a) < 0$이면 절댓값은 항상 $0$이상이므로 음수가 처음에 있던 수중 하나임을 알 수 있다.

$\text{Min}(a) \ge 0$이면 절댓값은 항상 $\text{Max}(a)$ 이하이므로 가장 큰 수가 처음에 있던 수임을 알 수 있다.

B. Minimize Permutation Subarrays

B. Minimize Permutation Subarrays

$n$이 $1,2$ 사이에 있게 만들 수 있다면 항상 subarray의 순열의 개수를 $2$개로 만들 수 있다. 그리고 이건 항상 최소이다.

$2$개는 $1$과 $1 \sim n$ 이다.

항상 $n$이 $1,2$ 사이에 있게 만들 수 있다.

$1, n, 2$ 라면 $1,2$ 의 위치를 변경

$n, 1, 2$ or $n,2,1$라면 $n$과 $1,2$ 중 인덱스가 작은것을 $n$과 swap

$1,2,n \ \text{or}\ 2,1,n$ 이라면 $1,2$ 중 인덱스가 큰 것을 $n$과 swap

세가지 케이스를 처리하면 된다.

C. No Prime Differences

C. No Prime Differences

내 풀이

바로 인접한 수의 차는 1이므로 소수가 아니다.

$m \not\in P$ 라면 그냥 쭉 나열해도 행간의 차이가 소수가 아니라서 문제가 되지 않는다.

$n \notin P$ 라면 아래로 증가하도록 나열하면 열간의 차이가 소수가 아니라서 문제가 되지 않는다.

$m \in P \ \text{and}\ n \in P$ 라 하자.

$1$행을 $1 \sim m$ 으로 나열하고 $[m+1,2m]$ 의 수들을 $2$행에 나열하는 방법이 있다.

$m+1$을 $m$ 바로 아래 붙이고 다른 모든 열들이 이전 행과 $m+1$ 만큼 차이나게 할 수 있다.

1  2  3  4  5
7  8  9 10  6
13 14 15 11 12

$m \in P$ 이고 $m+1$은 짝수여서 소수가 아니다.

void solvec() {
   int Y, X;
   cin >> Y >> X;
   if (!prime(X)) {
      for (int y = 0; y < Y; y++) {
         for (int x = 0; x < X; x++) {
            cout << y * X + x + 1 << ' ';
         }
         cout << endl;
      }
   } else if (!prime(Y)) {
      for (int y = 0; y < Y; y++) {
         for (int x = 0; x < X; x++) {
            cout << x * Y + y + 1 << ' ';
         }
         cout << endl;
      }
   } else {
      vvi ans(Y, vi(X));
      int c = 1;
      for (int y = 0; y < Y; y++) {
         int sx = md(X, -y);
         int x = sx;
         do {
            ans[y][x] = c++;
            x = md(X, x + 1);
         } while (x != sx);
      }
      for (int y = 0; y < Y; y++) {
         for (int x = 0; x < X; x++) {
            cout << ans[y][x] << ' ';
         }
         cout << endl;
      }
   }
}

에디토리얼 풀이

각 행당 $[1 + (i-1)m, im]$ 의 수들을 포함하는건 동일하다.

근데 이제 행 순서를 잘 재배열해서 $m$ 만 차이나는 행이 없게 만드는 것이다.

$2m$이나 $3m$은 $n,m \ge 4$ 여서 항상 소수가 아니기 때문에 가능하다.

$\left\lceil \dfrac{n}{2} \right\rceil$개의 앞선 행은 $1,3,5$ 를 차지하게 하고 $\left\lfloor \dfrac{n}{2} \right\rfloor$개의 뒤에 나오는 행들은 $2,4,6,\dots$를 차지하게 하면

항상 행의 차이가 $k \cdot m ~ (k \ge 2)$ 가 되게 할 수 있다.

D. Bracket Walk

D. Bracket Walk

이 문제는 그냥 에디토리얼 풀이를 정리한다.

---

우선 $n$이 홀수라면 불가능하다.

$1-indexed$에서 집합 $A$를 $i$ 가 짝수인데 $s_i=($ 인 인덱스와 $i$가 홀수인데 $s_i=)$ 인 인덱스의 인덱스 집합이라고 하자.

$A$가 공집합이면 $s=()()()\cdots$ 이므로 walkable하다.

$\text{Min}(A)$가 홀수라면 $()()))\cdots$ 처럼 된다는 의미이므로 not walkable하다.

왜냐면 앞에 $(($가 있어서 더 추가해줄 수 있는 방법도 없는데 balance가 음수가 되버리기 때문이다.

$\text{Max}(A)$가 짝수라면 $\cdots(()()$ 와 같은 형태이다. 비슷한 이유로 불가능하다.

그렇지않고 $\text{Min}(A)$가 짝수이고, $\text{Max}(A)$가 홀수이면 항상 가능하다.

이런 경우 $()()()((\cdots))()()$ 같은 형태인데, 앞의 $(($ 에서 왓다갔다 거리면서 적당히 수를 만들고 뒤에서 $))$ 에서 왔다리 갔다리 거리면서 수를 맞춰주면 된다.

따라서 모든 쿼리에서 $A$를 set 같은것으로 관리해주면 되고 $O((n+q)\log n)$ 정도가 걸린다.

E. Count Supersequences

E. Count Supersequences

에디토리얼을 참고했고, 해설이 DP얘긴 굳이 안해도 되는데 뜬구름 잡는다.

그래도 고려해볼만한 DP 점화식도 얻어간다.

---

$dp[i][j]=$ 길이 $i$의 수열이고 수열에서 subsequence로 나타나는 $a$의 가장 긴 prefix의 길이가 $j$ 인 배열의 개수라고 하자.

그럼 정답은 $dp[m][n]$ 이다.

다음과 같은 케이스들을 고려한다.

1. $i$ 번째가 $a$의 $j$ 번째 원소가 되는 경우, $dp[i-1][j-1]$
2. $i$ 번째가 $a$의 $j$ 번째가 되지 않는 경우 $dp[i-1][j]$ 에서 $i$ 번째를 채워줄 $k$ 개의 선택지가 있고, 여기서 $a_{j+1}$ 을 고르면 가장 긴 prefix의 길이가 $j$가 아닌 $j+1$가 되므로 $(k-1) \cdot dp[i-1][j]$
3. 2번과 동일한데 $j=n$ 이라 $a$가 모두 완성되었기 때문에 아무거나 골라도 되는 경우 $k \cdot dp[i-1][j]$

즉, 점화식은 다음과 같다.

$$ dp[i][j]=\begin{cases} dp[i-1][j-1]+(k-1)dp[i-1][j] & \ \text{if}\ j < n \\ dp[i-1][j-1]+k \cdot dp[i-1][j] & \ \text{otherwise}\ \end{cases} $$

이 DP는 $O(nm)$이 걸리기 때문에 직접 채울 수 없다.

시간복잡도를 줄일 아이디어는 식의 결과가 $a$의 형태에 의존성이 없다는 것이고, $a_i$를 아무거나 설정할 수 있다는 것에 있다.

$a_i \coloneqq 1$ 을 하자.

그럼 문제는 얼마나 많은 $1 \sim k$의 수만 포함하며 $1$을 최소 $n$개 가지는 $m$ 길이의 배열이 있냐를 구하는 문제로 바뀐다.

길이 $m$의 배열의 경우의 수는 총 $k^m$ 개이고, 여기서 $1$이 $0 \sim n-1$ 개 들어가는 경우의 수를 모두 빼주면

$$ k^m-\displaystyle \sum_{i=0}^{n-1} \dbinom{m}{i} \cdot \left( k-1 \right)^{m-i} $$

가 된다.

다른건 대충 거듭제곱으로 구해주고 $\dbinom{m}{i}$ 를 어떻게 구해줘야 하는지 보자. $m \le 10^9$ 이기 때문이다.

$\dbinom{m}{0}=1$ 이다.

$\dbinom{n}{k}=\dfrac{n!}{(n-k)!k!}=\dfrac{n \cdot (n-1) \cdots (n-k+1)}{k \cdot (k-1) \cdots 1}$

$\dbinom{n}{k+1}=\dfrac{n \cdot (n-1) \cdots (n-k+1) \cdot (n-k)}{(k+1) \cdot k \cdots 1}$ 이다.

따라서 $\dbinom{m}{i} \to \dbinom{m}{i+1}$로 가는 방법은 $(i+1)$로 나누고 $n-i$ 를 곱해주는 것이다.

ll poww(ll a, ll b) {  
   ll ret = 1;  
   while (b) {  
      if (b & 1) {  
         ret *= a;  
         if (~mod) ret %= mod;  
      }  
      a *= a;  
      if (~mod) a %= mod;  
      b >>= 1;  
   }  
   return ret;  
}  
inline int inv(int x) {  
   return poww(x, mod - 2);  
}  
  
void solve() {  
   int n, m, k;  
   cin >> n >> m >> k;  
   vi a(n);  
   fv(a);  
   int ans = poww(k, m);  
  
   int bino = 1;  
   for (int i = 0; i <= n - 1; i++) {  
      debug(bino, i);  
      int t = md(poww(k - 1, m - i) * bino);  
      ans = md(ans - t);  
      bino = md(md(bino * (m - i)) * inv(i + 1));  
   }  
   cout << ans << endl;  
}

F. Stuck Conveyor

F. Stuck Conveyor