Codeforces Round #726 (Div. 2)

종강 후 오랜만에 버추얼을 돌았다.

 

A. Arithmetic Array

주어진 수열의 길이를 n, 합을 x라 하고, 새로 추가한 수들의 개수를 m, 그 합을 k라고 하면 아래와 같은 식으로 표현할 수 있다.

x - n이 0 이하이면, m=1로 하고 k가 x-n-m이면 성립한다.

x - n이 0 초과이면, k=0로 하고 (즉, 새로 추가할 모든 원소를 0으로 하고) m을 x-n이면 성립한다.

따라서 x - n이 0 이하일 때 1개, 0 초과일 때, x-n개 추가하면 항상 성립한다.

 

B. Bad Boy

이동 거리는 맨하탄 거리라고 할 수 있다. 따라서 경로와 무관하게 이동 거리는 가장 먼 두 점이다.

그림에서처럼 (0, 0)과 (N, M)으로 하면 이동 거리를 최대로 할 수 있다. 

 

C. Challenging Cliffs

일단 주어진 수열 h을 정렬한다. 첫 번째 조건인 |h_1 - h_n|이 최소가 되도록 하기 위해서, 수열을 순회하면서 인접한 원소끼리 차이가 가장 작은 원소 둘을 선택한다. 선택한 원소의 위치를 a, b라고 해보자.

두 번째로 h_i ≤ h_{i+1}인 위치가 최대한 많게 배치해보자. h_j, h_{j+1}, ... , h_n,   h_1, h_2, ... , h_i 순서로 한다면 h_n과 h_1 한 번을 제외한 나머지 모든 경우가 조건을 만족하므로 최대이다. 여기서 만약 길이가 2일 경우에는 h_j > h_i 일 수 있다. 이러한 경우도 고려해보면 h_i, h_{j+1}, ... , h_n,   h_1, h_2, ... , h_j 순서로 배치할 수 있다.

 

D. Deleting Divisors (업솔빙)

아직도 게임 쪽은 전혀 감이 없다. 해설을 보았으나 그만 정신이 혼미해졌다. dp로 100까지 돌려본 뒤, 규칙을 발견하였다. dp식은 다음과 같다. x의 약수 중, k != 0, k != x인 k에 대하여, dp[x][a] = !(dp[x - k_1][!a] && dp[x - k_2][!a] && ... && dp[x - k_n][!a])

n이 2의 홀수 제곱일 경우는 무조건 Bob이 승리, 그 외의 경우에는 홀수엔 Bob, 짝수엔 Alice가 승리한다.

 

E1. Erase and Extend (Easy Version)

사전 순 비교이므로 앞쪽의 문자가 무조건 우선이다. 따라서 두 번째 연산으로 복사해 나가기 전에, 일단 적절히 잘라내서 최적의 prefix를 만들어야 할 것이다.

길이가 1부터 n인 prefix를 만들고 복사해서 n개의 문자열들을 만든다. 입력이 충분히 작으므로, 이 문자열들을 전부 비교해보고 가장 작은 문자열을 찾아도 된다.