코포 일기 : Codeforces Round #726 (Div.2)

대회 결과

실시간에서는 5솔에 성공. 그러나 채점도중 채점 데이터에 의해 E1번이 터졌다. 확인해보니 등식 하나를 잘못 쓰는 어이 없는 실수였다. 이 코드로 대회 도중의 데이터를 통과한 게 신기했다. 어찌됐든 간에 지난번보다 훨씬 나은 결과였고, 나름대로 만족스럽다.

 

A : Arithmetic Array

배열의 평균이 1이라는 것은 다르게 말하면 모든 원소의 합 = 원소의 갯수 라는 것이다. 그리고 0을 추가하면 원소의 갯수가 1 추가되므로 평균이 1보다 클때는 원소의 합 - 원소의 갯수만큼의 0을 추가해줘야 평균이 1이 된다.

평균이 1보다 작을 때는 항상 원소의 합 + x = 원소의 갯수 + 1 을 만족시키는 음이 아닌 정수 x가 항상 존재하므로 1개의 원소를 추가하며, 정확히 1일때는 추가할 필요가 없다.

 

B : Bad Boy

안톤의 위치가 어디에 있든 방의 각 모서리에 요요를 두는 것이 최적이다. 이는 간단하게 증명 가능한데, 양 쪽 모서리 (1,1), (m,n) 에 요요 A와 B가 있다고 가정하자. 안톤이 A를 줍고 B를 줍는다고 했을 때, 안톤의 이동 거리는 처음 위치 - A위치 간의 거리와 A위치 - B위치 간의 거리의 합이다. A위치 - B위치 간의 거리는 양 쪽 모서리에 있을 때가 최대임을 알 수 있다. 여기서 A를 한 칸 움직이면 처음위치 - A위치 간의 거리는 1 변화한다. 그러나 A위치 - B위치 간의 거리는 항상 1 감소한다. B - A 순서로 이동하는 경우에도 동일하다. 따라서 모서리에 냅두는 것이 이동 거리를 최대화하는 최적의 전략임을 알 수 있다.

 

C : Challenging Cliffs

오름차순 정렬 후 차이가 가장 적은 두 원소 위치를 골라 s, e라고 하면 s - e이후 원소들 - s이전 원소들 - e 순서로 배치하는 것이 최적이다. 이런식으로 배치하면 쭉 증가하다가 1번 떨어졌다가 다시 쭉 증가하는 형태가 나오기 때문에 항상 최적임을 쉽게 알 수 있다.

 

D : Deleting Divisors

꽤 어려웠다. 풀 당시에는 DP로 적은 n에 대하여 답을 구해놓고 나열해서 규칙을 찾았다.

n이 1인 경우 1을 제외한 약수가 없으므로 항상 후공이 이긴다. 그리고 n이 2이상인 경우에는 3가지 경우를 생각해보자.

ㄱ : n이 홀수인 경우

ㄴ : n이 짝수이면서 2의 거듭제곱 꼴인 경우

ㄷ : n이 짝수이면서 2의 거듭제곱 꼴이 아닌 경우

ㄱ의 경우 n의 약수는 항상 홀수이다. n의 약수인 d에 대해 n - d는 항상 d로 나누어 떨어지므로 n - d는 짝수이면서 2의 거듭제곱 꼴이 아니다. 즉, n - d는 ㄷ에 해당한다.

ㄷ의 경우 1이 아닌 홀수인 약수가 항상 존재한다. 이를 빼주면 항상 홀수임을 알 수 있다. 뺄 때마다 숫자는 항상 줄어드므로 ㄱ -> ㄷ -> ㄱ -> ... 가 반복되면 마지막에는 상대방에게 1을 안겨줄 수 있다. 따라서 ㄷ의 경우 항상 선공의 승리이며, ㄱ의 경우 항상 후공의 승리이다. 일반화하면 n이 1을 포함하는 모든 홀수일 경우 후공이 이긴다고도 할 수 있다.

ㄴ의 경우 할 수 있는 선택은 n/2를 빼거나, 다른 약수를 빼는 경우로 나뉘는데, 둘 다 항상 짝수이지만 n/2가 아닌 다른 약수를 뺀 결과는 짝수이면서 2의 거듭제곱 꼴이 아니므로 ㄷ의 경우, 즉 상대가 승리하는 경우이다. 따라서 최선의 선택은 n/2를 빼서 n -> n/2 -> n/4 -> ... 을 반복시키는 경우인데, 이 경우 n이 2의 홀수 거듭제곱인 경우 선공의 승리, n이 2의 짝수 거듭제곱인 경우 후공의 승리임을 알 수 있다.

 

E1 : Erase and Extend (Easy Version)

n개 삭제(최소한 길이 1 이상의 문자열이 남도록) -> 길이가 k이상이 될때까지 복사 -> 길이가 k가 될때까지 삭제

이를 1이상의 모든 n에 대해 해보고 사전순으로 앞서는 것을 찾으면 된다.