Codeforces Round 877 (Div. 2)


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

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

image.png

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

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

A. Blackboard ListPermalink

A. Blackboard List

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

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

B. Minimize Permutation SubarraysPermalink

B. Minimize Permutation Subarrays

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

22개는 111n1 \sim n 이다.

항상 nn1,21,2 사이에 있게 만들 수 있다.

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

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

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

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

C. No Prime DifferencesPermalink

C. No Prime Differences

내 풀이Permalink

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

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

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

mP and nPm \in P \ \text{and}\ n \in P 라 하자.

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

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

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

mPm \in P 이고 m+1m+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;
      }
   }
}

에디토리얼 풀이Permalink

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

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

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

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

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

D. Bracket WalkPermalink

D. Bracket Walk

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


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

1indexed1-indexed에서 집합 AAii 가 짝수인데 si=(s_i=( 인 인덱스와 ii가 홀수인데 si=)s_i=) 인 인덱스의 인덱스 집합이라고 하자.

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

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

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

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

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

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

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

E. Count SupersequencesPermalink

E. Count Supersequences

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

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


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

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

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

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

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

dp[i][j]={dp[i1][j1]+(k1)dp[i1][j] if j<ndp[i1][j1]+kdp[i1][j] otherwise  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)O(nm)이 걸리기 때문에 직접 채울 수 없다.

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

ai1a_i \coloneqq 1 을 하자.

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

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

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

가 된다.

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

(m0)=1\dbinom{m}{0}=1 이다.

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

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

따라서 (mi)(mi+1)\dbinom{m}{i} \to \dbinom{m}{i+1}로 가는 방법은 (i+1)(i+1)로 나누고 nin-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 ConveyorPermalink

F. Stuck Conveyor

Comments