Codeforces Round #691, #692 후기

저번 주말에 연달아 열린 Codeforces Round #691, #692에 모두 참가하였다. #691은 말아먹고, #692는 꿀 빨았다. 결과적으로 2600대로 레이팅을 복구했다. PS 감이 돌아오고 있다는 뜻이라고 믿고 싶다..

---

#691은 총 6문제였는데, A와 B를 빠르게 풀고 그대로 망했다.. 그래도 2문제를 빨리 푼 덕에 146등을 해서 폭삭 망하지는 않았다. 레이팅 변화는 -22. (2579 -> 2557)

 

A(2min) : 길이가 각각 N, M인 두 수열 \( A, B \)가 주어지면 모든 \( B_i \) 에 대해 \( gcd(A_1 + B_i, A_2 + B_i, \cdots, A_N + B_i) \) 의 값을 구하면 된다.

\( gcd(a, b) = gcd(a, a-b) \) 라는 사실을 이용하면 구하는 값이 \( gcd(A_1 + B_i, A_2 - A_1, A_3 - A_2, \cdots, A_N - A_{N-1} ) \) 이 되므로 전처리를 해 두면 B의 원소 하나당 gcd 한 번으로 답을 구할 수 있다.

 

B(16min) : 유리병이 N개 있는데, 각각은 용량이 \( a_i \)이고 현재 \( b_i \) 만큼의 물이 차 있다. 하나의 유리병에서 다른 유리병으로 물을 옮길 수 있는데, 원하는 양만큼 따를 수 있지만 병에 따르는 양과 같은 양만큼 바닥에 흘린다. 모든 가능한 K에 대해, 유리병 N개 중 K개를 잘 골라 거기에 물을 다 모은다고 했을 때 최대로 모을 수 있는 물의 양을 구하여라. 입력의 모든 정수는 1 이상 100 이하.

우선 물이 2번 이상 옮겨다니는 것은 무조건 손해임을 알 수 있다. 물을 모을 병의 집합이 정해지면 그냥 다이렉트로 부으면 되기 때문이다. 그리고, 물을 모으기로 한 병 집합에 대해 용량의 합이 \( x \), 이미 들어있는 물 양의 합이 \( y \)라고 하고 모든 병에 대해 들어있는 물 양의 합이 $s$라고 하면 병 집합에 모을 수 있는 최대 물의 양은 \( min(y+s, 2x)/2 \) 임을 알 수 있다.

이제, 입력이 작기 때문에 대충 \( 100^4 \) 정도 시간에 도는 knapsack DP를 짤 수 있다. D[i][j][k] = "1~i번째 물병 중 j개를 골랐을 때 용량의 합이 k일 경우 가장 많이 확보할 수 있는 물 양의 합"으로 정의하면 상태가 총 \( 100^4 \)개 정도 있고 각 상태마다 \( O(1) \)만에 계산이 된다. K에 대한 답은 \( max(min(2 * x, D[n][K][x] + s) / 2) \) 으로 구해진다.

 

C : \( N \times N \) 라틴 방진이 주어지면 행/열 cyclic shift, 행/열 각각에 대해 순열을 inverse로 바꾸기 쿼리를 빠르게 수행해야 한다.

나는 아예 모르겠었는데, 라틴 방진을 \( ( i, j, a_{ij} ) \) tuple이 \( N^2 \)개 있는 걸로 생각하면 각 쿼리가 이쁘게 바뀐다고 한다. 풀이를 듣고 또 한 번 벽을 느꼈다..

 

D : 길이 N짜리 binary string이 주어진다. 이 string에 다음 연산을 적용할 수 있다.
- 0과 1의 개수가 같은 substring을 골라서, 0은 1로 바꾸고 1은 0으로 바꾼 다음에 뒤집는다.
0번 이상의 연산을 통해 얻을 수 있는 가장 사전 순으로 빠른 string을 구하여라.

똑같은 연산을 2번 하면 원래대로 돌아오기 때문에 string들은 동치류 관계로 묶인다. 이제 naive로 동치류를 구하는 코드를 짜서 규칙을 찾으면 풀리겠다고 생각했는데... 그냥 찍어보면 규칙이 전혀 보이지가 않는다.

0이 나오면 한 칸 올라가고 1이 나오면 한 칸 내려가는 그림(괄호 문자열 할 때 많이 나오는 그림)을 생각하면 연산의 의미는 "같은 높이인 두 점을 골라 두 점 사이의 선을 좌우로 뒤집는 것"이 되는데, 나는 거기까지만 발견했고 더 가지 못했다.

동치류의 규칙은 방금 말한 그림에서 모든 x에 대해 "높이가 x인 점의 개수"가 다 같은 것이라고 한다. 뻘짓을 덜 했으면 풀었을까 싶기도 하다..

 

E : 돌더미 a, 돌더미 b의 2개의 더미가 있는 nim game을 진행한다. 그런데, N개의 상태가 추가적으로 주어지는데, 이는 각 \( (a_i, b_i) \)에 대해 "돌더미 a에 \(a_i\)개, 돌더비 b에 \(b_i\)개가 있는 상태"가 되면 다음 번에 움직여야 하는 사람이 진다는 뜻이다. 이 때, 쿼리로 상태 여러 개가 주어지면 선공의 승패를 판정하여라.

생각을 별로 안 해 봤는데, 풀이를 듣기로는 2차원 평면상에서 선공이 지는 지점이 기울기 1인 선분 \( O(N) \)개로 나타나고, 그걸 잘 구할 수 있다고 한다. 애초에 C랑 D한테 털려서 접근도 못 한게 아쉽다.

 

F : 안 읽었다.

---

#692는 역시 6문제였고, 이번에는 A, B, C, E의 4문제를 풀어서 35등으로 떡상했다. 레이팅 변화는 +96. (2557 -> 2653) predictor는 오차가 약간 있는 듯..

 

A(8min) : N x N 체스판에 M개의 룩(Rook)이 서로 공격당하지 않는 상태로 있다. 모든 룩들을 체스판의 주대각선 (행 번호 = 열 번호인 칸) 위로 옮기려고 할 때, 최소 이동 횟수를 구하여라.

이미 주대각선 위에 있는 룩은 건드릴 필요가 없으니 무시하자. 주대각선 위에 있지 않다면 그 룩은 한 번의 이동으로 (행 번호) 또는 (열 번호)에 해당하는 주대각선 칸에 갈 수 있다. 이제, 주대각선 칸을 정점이라 하고 각 룩은 두 개의 주대각선 칸을 잇는 간선이라고 생각하자. 이제 이 간선들로 그래프를 만들었을 때, 어떤 컴포넌트에 정점이 N개라면 N-1개 또는 N개의 룩이 관여되어 있음을 알 수 있다. (각 정점의 차수가 2를 넘을 수 없기 때문)

N-1개짜리 컴포넌트는 트리기 때문에 리프에 연결된 룩부터 하나씩 리프 위치로 옮기면 N-1번의 이동으로 다 옮길 수 있고, N개짜리 컴포넌트는 사이클 하나로 이루어져 있다는 뜻이므로 (모든 정점의 차수가 2) 룩 하나를 먼저 딴 데로 옮겨야지 나머지 룩들을 다 한 번의 이동으로 제자리로 보낼 수 있다 (즉, N+1번의 이동이 필요하다). 컴포넌트별로 이동 횟수를 다 합해주면 된다.

여담으로, M=N이면 사이클을 해결할 때 "딴 데로 옮기기"가 안 되기 때문에 불가능할 수도 있는데, 이 문제는 정말 친절하게도 M<N 조건이 걸려 있다. 물론 대회 중에는 이런 케이스는 당연히 생각도 안 했다 ^^;;

 

B(21min) : 길이 N짜리 Binary string이 있는데, 이 중 일부 문자는 아직 안 정했다. (입력에서 '?'로 표시) '?' 자리를 적절히 0 또는 1로 바꾸었을 때, 입력으로 주어지는 A와 B에 대해서 다음 값을 최소화하라.
- "A * (문자열의 "10" subsequence의 개수) + B * ("01" subsequence의 개수)"

바로 전 라운드 D에서 binary string에 탈탈 털렸기 때문에 약간 겁을 먹었는데, 다행히도(?) D가 아니고 B라서 좀 더 쉽게 풀 수 있었다. 핵심 관찰은 '?' 중 0이 몇 개인지를 정하면 ("01"의 개수 + "10"의 개수) 가 일정하다는 것이다. "00"의 개수 + "11"의 개수가 같기 때문이라고 생각하면 이해하기 편하다. 이제 Greedy 전략을 생각할 수 있는데, "01"이 "10"보다 싸다면 0을 최대한 앞으로 모는 것이 좋고, 더 비싸다면 반대로 뒤로 모는 것이 좋음을 알 수 있다. 이제 우리가 고려해야 하는 하는 문자열의 후보가 \( O(N) \)개로 줄었다!

그 다음 과정도 마냥 쉽지는 않고 좀 귀찮은데, ? 중 0이 k개인 문자열과 k+1개인 문자열은 딱 한 글자만 다르고 모두 같다는 사실을 이용하면 문자를 하나씩 바꿔가면서 바뀐 문자 앞/뒤에 있는 0/1 갯수를 가지고 열심히 계산을 해주면 전체 문제를 \( O(N) \)에 풀 수 있다.

 

C(41min) : 알파벳 소문자로 이루어진 길이 N짜리 문자열이 있다. 이 문자열에 대해 \(F(s, e)\)를 다음과 같이 정의한다.
- \( s < e \)일 경우, \( m \)을 하나 골라서 \( -F(s, m) + F(m + 1, e) \)의 값으로 한다.
- \( s = e \)일 경우, 문자열의 s번째 문자가 k번째 알파벳이라고 하면 \( 2^{k-1} \)이다.
위에서 나타나는 \( m \)을 모든 step에 대해 적절히 골라서 \( F(1, N) \)의 값이 입력으로 주어진 정수 T가 되게 할 수 있는지 없는지 판별하라.

규칙이 좀 난해한데, 일단 생각할 수 있는 것은 결국 문자열의 각 위치마다 값이 하나씩 있고, 이 값에 +1 또는 -1을 곱해서 모두 더하는 꼴이라는 것이다. 이제 +와 -가 어떻게 배당되느냐가 문제인데, 괜히 머리 굴리느라 시간 쓰지 말고(?) 가능한 모든 경우를 시뮬레이션 해보면 규칙이 생각보다 간단함을 알 수 있다. 규칙은 그냥 "N번째 문자는 +, N-1번째 문자는 -, 나머지 문자는 +, - 모두 가능"으로 요약된다.

이제 마지막 2문자에 대한 값을 잘 빼준 다음, 나머지 N-2개의 문자에 대해서는 T를 적절히 바꾸어서 +/-가 아니라 0/1 knapsack, 즉 "고르거나 말거나"로 문제를 변형할 수 있다. T의 값이 큰 것이 문제인데, 여기서는 각 문자에 걸린 값이 2의 제곱 꼴이기 때문에 자주 쓰이는 그리디 알고리즘 하나로 가능 여부를 바로 판정할 수 있다 : 값들을 큰 것부터 보면서 가방에 넣을 수 있으면 넣는다. 마지막에 가방이 다 차있으면 Yes, 아니면 No.

 

D : 길이 N짜리 순열 \( P \)가 주어진다. 초기에 \( A_i = i \)인 길이 N짜리 수열이 하나 있는데, 수열 \( A \)에 다음 연산을 수행할 수 있다.
- 어떤 \( i (1 \le i \le N) \) 에서 시작하여 \( P[i], P[P[i]], \cdots \) 로 계속 가다가 \( i \)로 다시 돌아올 때까지 만난 인덱스들에 대해, \( A_i \)의 값을 \( A_{P[i]} \)로 옮기고, \( A_{P[i]} \)는 \( A_{P[P[i]]} \)로, ..., 하는 식으로 cyclic shift를 수행한다.
이제 매일마다 수열 \( A \)에 연산을 원하는 만큼 수행하여 이전에 한 번도 나타나지 않은 상태로 바꿀 것이다. 만약 그렇게 할 수 없는 날이 오면 과정을 끝낸다.
최대한 많은 날동안 연산을 수행할 수 있도록 \( P \)에서 두 개의 원소를 골라 바꾸는 것을 0번 이상 할 것이다(인접한 두 원소가 아니어도 된다). 이 때, "최대로 수행 가능한 연산 수 (mod 10억7)"와 "그것을 얻기 위해 \( P \)에서 수행해야 하는 최소 교환 횟수"를 구하여라.

순열은 사이클 여러 개로 분해할 수 있다. 사이클 하나당 (사이클 길이) 만큼의 서로 다른 상태가 나오고, 사이클들은 서로 독립적이기 때문에 순열이 주어지면 거기서 만들 수 있는 서로 다른 상태의 개수는 사이클 분할을 수행해서 나온 각 사이클의 길이들을 모두 곱한 값이다. 이것을 최대화하기 위해 생각을 해 보면, 길이가 3 초과인 사이클은 만들 필요가 없음을 알 수 있고 또 길이가 2인 사이클 3개보다 3인 사이클 2개가 더 좋음을 알 수 있다. 표현 방식은 여러 가지가 있겠지만, 가장 간단한 방법은 (ainta님의 코드에서 쓰인) 아래 방법이다.

- \( D[1] = 1, D[2] = 2, D[3] = 3, D[4] = 4, D[k] = 3D[k - 3] (k \geq 5) \)

이제 실제로 사이클 분할이 그렇게 되도록 \( P \)를 잘 바꾸어야 하는데, \( P \)에서 어떤 두 원소의 위치를 바꾸는 것은 사이클 하나를 둘로 쪼개거나 사이클 두 개를 하나로 합치는 연산임을 알 수 있다. 이제 큰 사이클은 잘 쪼개고, 작은 사이클은 잘 합쳐서 3 잔뜩과 2 약간을 만들면 될 것 같다..

그런데 이게 케이스가 좀 심상치 않다. 나는 다 구현하지 못한 채로 대회가 끝났는데, 맞은 코드들을 보면 하나같이 if문이 잔뜩 떡칠되어 있다. 심지어 2를 2개 쓰는 경우에는 이것을 4 하나로 바꿔도 답이 같기 때문에 그 경우도 고려해줘야 한다. 아무튼 별로 좋은 문제는 아닌 거 같다.

 

E(89min) : 정점 N개, 간선 M개짜리 DAG가 하나 주어진다. 이 그래프의 정점들 위에 말을 0개 이상 놓은 상태로 두 사람이 선공/후공 게임을 진행하는데, 각 차례마다 해당하는 사람은 말 하나를 골라 그 말이 위치한 정점에서 갈 수 있는 다른 정점 중 하나로 옮긴다. 한 정점에 말이 몇 개 있든지 상관 없다. 만약 자기 차례에 말을 옮길 수 없어지면 진다. 이제, 다음과 같은 과정을 생각해 보자.
- 처음에는 그래프 위에 말이 하나도 없다.
- 매 시도마다, \( [1, N+1] \) 범위에서 정수를 하나 고른다.
- 고른 정수가 \( N \) 이하이면, 해당하는 번호의 정점에 말을 하나 추가한다.
- 고른 정수가 \( N+1 \) 이면, 이 과정을 멈추고 그래프에서 게임을 시작한다. 
과정에 따라 게임을 진행했을 때, 선공이 이길 확률을 구하여라.

(* Grundy Number 및 Gauss-Jordan Elimination에 대한 사전 지식이 필요하다. *)
우선, 게임의 정의상 Grundy Number가 아주 잘 정의된다. 말 하나의 Grundy Number는 DAG에서 DP를 해서 쉽게 구할 수 있고, 각 말이 독립적으로 움직이기 때문에 모든 말의 Grundy Number를 XOR하면 게임의 Grundy Number도 구해진다. 그리고 또 하나 관찰할 중요한 사실은 Grundy Number의 최댓값이 \( O(\sqrt{M}) \) 이라는 것이다. Grundy Number의 정의상, 어떤 정점의 Grundy Number가 K 이상이려면 적어도 K개의 간선이 연결되어 있어야 하고 또 Grundy Number가 \( [0, k-1] \). 구간에 속하는 정점이 모두 필요하기 때문이다. 문제 제한으로 따져 보면 대충 \( 2^9 = 512\) 미만임을 알 수 있다.

이제, 위의 과정을 현재 게임의 Grundy Number가 x인 상태에서 시작했을 때 선공이 이길 확률을 \( E_x \) 라고 정의하자. 상황을 그대로 식으로 옮겨 보면 \((N+1)E_x = E_{x \oplus g(1)} + E_{x \oplus g(2)} + \cdots + E_{x \oplus g(N)} + h(x) \) 가 된다. (\(g(i)\) : i번 정점의 Grundy Number, \(h(x) = \) (x가 0이면 0, 아니면 1))

각각의 식에서 \( E_x \) 꼴 항들의 계수는 식 하나당 \( O(N) \)에 계산이 되므로, 이들을 모두 좌변으로 옮기고 정리하면 \( x = 0, 1, \cdots, 2^9 - 1 \) 에 대해 총 \( 2^9 \)개의 선형 관계식이 나온다. 이를 행렬로 표현한 다음에 Gauss-Jordan Elimination으로 풀면 \( E_x \)의 값을 모두 구할 수 있다. 이제 문제의 답은 \( E_0 \)이므로 그냥 출력하면 끝이다.

시간복잡도가 대충 \( O(512^3) \) 이고 modular 연산이라 좀 빡빡하다고 생각할 수 있는데, 적당히만 짜면 for문 구조상 실제로는 상수가 대충 1/3 정도 되기 때문에 제한 시간 안에 충분히 나온다. modualr inverse를 \( O(N^3) \)번 계산하지 않도록 주의. 사실 그냥 그럴듯한 구현체를 찾아서 복붙해도 무방하다 ㅋㅋ 

 

F : 안 읽었다.