Educational Codeforces Round 86

이 라운드에서 Rated 되는 참가자 중 60등을 하며 레이팅을 +106 올려 2,204의 레이팅으로 Master(오렌지)가 되었다. 알고리즘 처음 시작할 때 목표가 오렌지 가는 거였는데, 2년 반 보다는 조금 길고, 3년 보다는 조금 짧은 시간이 흘러 도달했다는게 나름 뿌듯하다. 이를 계기로 알고리즘 공부를 다시 열심히 할까 싶다. 사실 대회 중간에 꿀잠 잤던건 안비밀

문제 풀이

이번 대회에 대한 문제 A ~ F 중 내가 대회중에 해결한 5문제에 대한 풀이를 기록해둔다. (대회 문제 링크)

A. Road To Zero

다음 두 가지 전략 중 하나가 최선임을 알 수 있다:

• 둘 중 작은 값이 0이 될 때 까지 두 수 모두를 바꾼 후, 나머지 하나의 수를 0으로 만든다.
• 하나의 수를 0으로 만들고, 이후 다른 하나의 수를 0으로 만든다.

두 전략에 대한 cost를 각각 계산해주고, 이 중 더 작은 값을 출력하면 된다.

B. Binary Period

Solution 1.

각각의 $t$의 부분문자열(인접한 위치에 있는 것)을 길이가 짧은 것 부터 하나씩 살펴보며, 다음을 수행하자:

• 해당 부분문자열을 길이가 $2|t|$가 될 때 까지 복붙하여 만든 문자열을 $s'$이라 할 때, $t$가 $s'$의 부분 문자열이 되는지 확인한다.
• 만약 그렇다면, $s'$을 출력한다.

시간복잡도는 총 $O(|t|^3)$이다. 다만, 이 풀이의 정당성이 그리 직관적이지는 않을 수 있으나, 문제의 정답이 되는 문자열의 길이가 최대 $2$라는 사실을 확인하고 나면, 정당함을 알 수 있다. 그리고 이 관찰은 다음의 더 깔끔한 풀이를 만들어준다.

Solution 2.

모든 문자열 $t$는 길이 $2|t|$의 문자열 $\tt"0101\dots01"$ 또는 $\tt"1010\dots10"$의 부분문자열이다. 따라서, 문제의 정답이 $\tt "1"$ 또는 $\tt "0"$이 될 수 있는지만 확인해주면 된다. 시간복잡도는 $O(|t|)$이다.

C. Yet Another Counting Problem

먼저, $(x \bmod a) \bmod b = (x \bmod b) \bmod a$라면, $((x \bmod ab) \bmod a) \bmod b = ((x \bmod ab) \bmod b) \bmod a$이고, 이 역 또한 성립함을 확인할 수 있다. 따라서, 다음과 같이 문제를 해결할 수 있다.

 

각각의 $1 \le x \le ab$에 대해 $(x \bmod a) \bmod b = (x \bmod b) \bmod a$인지 확인해주고, 이 조건을 만족하는 $x$의 갯수를 prefix sum으로 처리해준다. 이후, 이를 이용해 각각의 쿼리를 처리해주면 된다.

D. Multiple Testcases

먼저, 문제의 답(최소 테스트 케이스 수)을 구해주자. 문제의 답은 크게 두 가지 방법으로 구할 수 있다.

• 문제의 답을 구하는 것을 "문제의 답이 $x$이하 인가?"를 판별하는 결정 문제로 바꿔준 후, 이분탐색을 이용하여 구한다.
• 크기 $i$이상의 배열의 수를 $d_i$라 하면, 문제의 답은 $\max_i \lceil d_i / c_i \rceil$이 됨을 관찰한다.

문제의 답을 $m$이라 하자. 각 배열들을 크기 순으로 정렬한 후, $i$번째 배열을 $(i \bmod m)$번 테스트 케이스에 추가해주면 문제의 답에 대한 실례를 구성할 수 있다.

E. Placing Rooks

$n = 1$이거나, $k = 0$인 경우 등 자명한 경우는 따로 처리해주고 나서 생각하자.

 

먼저, 모든 룩은 서로 다른 행 또는 서로 다른 열에 배치되어야 함을 관찰할 수 있다. 따라서, $k \ge n$일 수는 없다.

 

일반성을 잃지 않고, 모든 룩이 서로 다른 행에 배치되었다고 가정하자. 그러면 이 문제는 각 행의 룩을 $n-k$개의 열에 배치하되 각 열에 최소 하나의 룩을 배치하는 문제가 된다. $n$개의 룩을 $n-k$개의 집합으로 분할하는 경우의 수는 스털링수 $S(n, n-k)$이고, 각 집합에 해당하는 열을 선택하는 경우는 총 ${}_nP_{n-k} = n (n-1) \cdots (k +1 )$이다.

 

다음의 관계식을 이용하여 스털링 수를 계산하면, 총 $O(n)$ 시간에 문제를 해결할 수 있다.

$$ S(n, k) = { 1 \over k!}  \left( k^n - {k \choose 1} (k-1)^n + {k \choose 2} (k-2)^n - \cdots + (-1)^{k-1} {k \choose k-1} 1^n \right) $$