Codeforces Round #804

나는 원래 어려운 문제를 풀어내기보다는 쉬운~적당한 (solved.ac 기준 플레 이하) 문제를 빠르고 정확하게 풀어내는 것으로 승부하는 타입이었는데, 요즘 들어 그 능력마저 사라져 버린 것 같아 문제 의식을 느끼게 되었다. 그래서 한 동안 쉬었던 코포 Div2 돌리기를 다시 시작하기로 했다. 괜히 미루면 또 안 할 거 같아서 당장 있는 대회부터 바로 registration을 걸었다.

총평

난이도 커브가 ABC / D / E 단계로 수직상승하는 형태의 대회였다. 문제가 전체적으로 풀면서도 "내 풀이가 맞나..?" 싶은 생각이 많이 드는 형태였다. 증명 연습을 더 해야 하나..

그리고 E 같은 문제를 뚝딱 풀어내는 사람이 되려면 어떻게 해야 할지 모르겠다.

대회 후기

4215점. 58등이다. E를 어떻게 61명이나 푼 건지 모르겠다.

A번을 열고 약 1분간 고민에 빠졌다가 곧 정신을 차리고 풀 수 있었다.

B번은 다행히도 예제를 쳐다보니 풀이가 금방 보여서 빠르게 풀었다.

C번을 열고 약간 당황했는데, 역시 예제를 관찰하면서 대충 보이는 성질로 때려맞히니 생각보다 금방 풀 수 있었다. 여기까진 좋았는데...

D번을 딱 열고, 약간의 고민 끝에 풀이를 일단 찾아서 코딩을 했는데 내니까 틀렸다. 곧 왜 틀린지는 알았는데 고칠 방법이 아무리 생각해도 O(N^3) 짜리밖에 모르겠어서 뻘짓을 좀 하다가 E로 넘어가기로 했다.

E를 좀 보다가 이상한 관찰을 하나 하고, 그걸 바탕으로 대충 뭔가를 짜서 냈는데 틀렸다. 다시 생각해 보니 틀린 관찰이었다. 좀 더 생각하다가 모르겠어서 다시 D로 왔다.

D를 다시 한 번 보니 이번에는 O(N^2) 짜리로 고칠 수 있는 방법이 생각나서 금방 짜서 맞았다. 다 풀어 놓고 그거 하나 생각을 못 해서 시간을 날린 게 좀 아쉬웠다.

남은 시간에는 E를 계속 고민했는데, 피곤하기도 하고 내가 당장 고민한다고 풀 수 있는 문제가 아닌 듯 해서 그냥 풀이를 보기로 했다.

문제별 풀이

A

n이 홀수이면 불가능함을 우선 관찰하자. a^b, b^c, a^c의 1의 자리 수가 a, b, c의 홀/짝에 따라 어떻게 되는지 생각해 보면 알 수 있다.

n이 짝수라면, 변수가 3개나 있으면 복잡하니 일단 c=0이라 두면 a^b + a + b = n인 a와 b를 찾는 것으로 바뀐다. n이 짝수이기 때문에 a=b=n/2로 설정하면 a^b=0이 되어서 쉽게 위 식을 만족함을 알 수 있다.

즉, n이 홀수이면 불가능, n이 짝수이면 (a, b, c) = (n/2, n/2, 0) 으로 하면 된다.

코드 : https://codeforces.com/contest/1699/submission/162756526

B

2 x 2 행렬에 대해 가능한 답은 아래와 같은 형태이다.

0 1
1 0

예제의 첫 번째 케이스를 2 x 2 단위로 끊어서 보면, 똑같은 2 x 2 행렬을 가지고 한 쪽에만 모든 원소 not을 취해서 붙여 놓았다고 생각할 수 있다. 즉, 일반적으로 다음과 같이 배치를 한다고 해 보자.

0 1 1 0 ... 0 1
1 0 0 1 ... 1 0
1 0 0 1 ... 1 0
0 1 1 0 ... 0 1
...

이런 식으로 격자 구조를 만들면 임의의 짝수 n, m에 대해 n x m 행렬이 문제 조건을 만족함을 쉽게 알 수 있다. (꼭짓점 / 모서리 / 내부의 3가지 케이스 각각에 대해 살펴보자)

코드 : https://codeforces.com/contest/1699/submission/162758972

C

P[x] : A[i] = x인 i, Q[y] : B[j] = y인 j라고 각각 정의하자.

A와 B가 similar한 필요충분조건은 모든 k (0 <= k < n)에 대해 다음을 만족하는 것이다.

- min{P[0], P[1], ..., P[k]} = min{Q[0], Q[1], ..., Q[k]}
- max{P[0], P[1], ..., P[k]} = max{Q[0], Q[1], ..., Q[k]}

(증명: 어떤 k에 대해 위 조건 중 적어도 하나가 만족되지 않는다고 하면, 둘 중 하나에서 {0, 1, ..., k}를 포함하는 최소의 구간을 잡았을 때 반대쪽에서는 {0, 1, ..., k}가 모두 포함되지 않는 경우가 생기므로 similar하지 않게 된다.

반대로, similar하지 않다면 둘의 mex가 다른 구간을 잡았을 때 두 mex 값 중 큰 값을 m이라 하면 k = m에 대해 두 조건 중 하나가 만족되지 않음을 알 수 있다. mex 값이 m인 순열에서는 min / max 값 모두 구간 내에 포함되는데, 반대쪽 순열에서는 둘 중 하나가 구간 밖으로 나와 있어야 하기 때문)

이제 순열 A에 대해 위 조건을 만족하는 B의 개수를 구하는 것은 P[0], P[1], ..., P[n-1]을 순서대로 보면서 이것들의 prefix min/max 값을 갱신하면서 할 수 있다.

L[i] = min{P[0], ..., P[i]}, R[i] = max{P[0], ..., P[i]} 라고 하자. 순열 B에서 0, 1, 2, ..., (n-1)의 위치를 차례대로 결정한다고 할 때, 각 i가 들어갈 수 있는 위치의 가짓수는 다음과 같다.

- i == 0일 경우 1가지 (A와 동일한 위치에 와야 함)
- L[i] != L[i-1] 이거나 R[i] != R[i-1]일 경우 1가지 (역시 A와 동일한 위치에 와야 함)
- 나머지 경우 (R[i]-L[i]+1-i)가지 (L[i]와 R[i] 사이 빈 칸 중 아무데나 하나에 들어가면 됨)

위에서 구한 가짓수는 순열 B를 만드는 임의의 과정에서 항상 동일하므로 이를 모두 곱하면 답이 된다.

코드 : https://codeforces.com/contest/1699/submission/162763649

D

각 원소를 남길지 말지를 왼쪽부터 결정하며 DP를 한다고 해 보자. 다음과 같이 DP 식을 정의한다.

D[i] : i번째 원소를 마지막으로 남기기로 했을 때 최대로 남긴 원소 개수 (D[0] = 0)

같은 색의 원소들만 남겨야 하므로, j < i에 대해 D[j]에서 D[i]로 값을 가지고 오려면 일단 a[j] == a[i]를 만족해야 한다. (특수 케이스로, j == 0일 경우에는 항상 가능)

또한, 그 사이의 원소를 2개씩 잘 짝지어서 지울 수 있어야 한다. 즉, C(s, e)를 "a[s]부터 a[e]까지를 2개씩 잘 짝지어서 다 지울 수 있는가?" 로 정의했을 때 D[i]는 (j < i) && (j == 0 || a[j] == a[i]) && C(j+1, i-1) 을 만족하는 모든 j에 대해 D[j]+1의 최댓값이다.

C(s, e) 라는 함수의 값을 빠르게 얻어낼 수만 있다면 DP 계산은 O(N^2)이기 때문에 문제를 해결할 수 있다. 이를 빠르게 계산하기 위해서는 다음의 성질을 관찰하면 된다.

(C(s, e) == true) <=> (e-s+1이 짝수이고 a[s], ..., a[e] 중 과반수로 등장하는 원소가 없음)

과반으로 등장하는 원소가 있을 경우 불가능함은 자명하고, 없을 경우 가능함은 구간 길이에 대한 수학적 귀납법으로 보일 수 있다. (제일 많이 등장하는 애를 무조건 포함시켜서 지우면 됨)

이제 s를 고정하고 e를 한 칸씩 늘려가면서 위 조건을 만족하는지를 실시간으로 업데이트해주면서 모든 C(s, e) 값을 O(N^2)에 구해 놓을 수 있다. 그 값을 가지고 DP를 돌리면 전체 문제도 O(N^2)에 해결된다.

코드 : https://codeforces.com/contest/1699/submission/162790025

E (upsolved)

결국 우리가 풀고자 하는 문제는 입력에 주어진 각 수를 적절한 약수들로 인수분해하여 나타나는 수들의 (최댓값 - 최솟값) 을 최소로 만드는 것이다.

일단 생각할 수 있는 방법은, 각 수마다 "사용 가능한 약수의 하한"을 정하면 이제 등장하는 약수의 최댓값이 작을수록 좋음을 알 수 있다. 이제 이 하한을 1부터 (입력에 등장하는 수 중 최솟값)까지 모두 시도해 보면 답을 구할 수 있을 것이다. 즉, D[m][a] : "a의 인수분해에서 사용 가능한 약수 하한이 m일 때 등장하는 약수의 최댓값" 이라고 했을 때, 답은 1 <= k <= (입력 최솟값)에 대해 ((입력에 등장하는 a들에 대해 D[k][a]의 최댓값) - k) 중 가장 작은 값이다.

이걸 빠르게 계산하기 위해서는 D[k+1][*]들을 모두 안다고 할 때 D[k][*]를 빠르게 계산하는 법에 대한 관찰이 필요하다. k+1 -> k로 넘어올 때 달라지는 점은 "각 수의 인수분해에 k를 사용할 수 있다" 밖에 없으므로, 우선 k의 배수가 아닌 a에 대한 D[k][a]는 D[k+1][a]와 동일함을 알 수 있다. 그럼 이제 c >= k에 대해 D[k][ck] 꼴의 값만 다시 계산하면 되는데, (c < k일 경우 ck의 분해에 k를 사용하게 되면 c가 남아버려서 하한 k를 만족할 수 없음) 이는 매우 간단하게 D[k][ck] = min(D[k+1][ck], D[k][c]) 라는 식으로 계산할 수 있다.

즉, D[k+1][*]를 저장한 배열이 있다고 하면 여기서 값을 많아야 m/k개만 바꿔서 D[k][*]를 저장한 배열을 얻을 수 있는 것이다. 이를 k=m에서 k=1까지 다 하면 m/1 + m/2 + ... + m/m 이므로 시간복잡도가 O(mlogm)이다. 참고로 실제로는 각 k에 대해 k*k, (k+1)*k, ..., 꼴의 수만 갱신이 일어나는데, 이 경우 시간복잡도가 O(mloglogm) 임이 알려져 있다.

이제 답을 빠르게 계산하는 문제가 남는데, 이것은 하한을 m에서 1로 감소시킴에 따라 각각의 DP값 역시 감소하기만 한다는 성질을 이용하면 다음과 같은 카운팅 배열과 변수를 관리하며 전체 DP값 중 최댓값을 계속 update해줄 수 있다.

- C[k] : (현재 DP값)=k인 원소의 개수
- mx : C[k]>0인 k 중 최댓값

코드 : https://codeforces.com/contest/1699/submission/162853005