Codeforces Round #730 (Div. 2)

컨디션이 다시 올라왔고 잘 풀어서 기분이 좋다.

 

A. Exciting Bets

두 음이 아닌 정수 a, b가 주어졌을 때 적절한 연산을 하여 gcd(a, b)를 최대로 하는 문제이다. 먼저, 문제에 제시된 대로 0, 0이라면 INF라고 하니 $a = b$인 경우는 0, 0으로 만들면 될 것이다. $a \ne b$인 경우, $gcd(|a-b|, 0)$ 인 상태가 최대이다.

이는 $gcd(a, b) = gcd(a-b, b)$임을 통해 확인할 수 있다. 라운드 중에는 위의 등식이 생각나지 않아서 직접 예제를 만들어보다 보니 우연찮게 발견했다. 맞았으니 다행이긴 한데 많이 아쉬웠던 풀이.

 

B. Customising the Track

수열이 주어졌을 때 $\sum_{i=1}^n \sum_{j=i+1}^n | a_i - a_j |$이 최소가 되도록 적절히 연산을 하는 문제이다. 연산을 했을 때 수열의 원소의 합은 보존되기 때문에, 수열의 원소들에 최대한 균등하게 분배할 때가 최선이다. 따라서 n-reminder개의 sum/n과, reminder개의 sum/n+1가 구성된다.

 

C. Need for Pink Slips

$0.1 \leq v$이므로 c, m, p에 대하여 각각 최대 10번씩 밖에 선택되지 않는다. 따라서 완전탐색으로 모든 경우를 확인해볼 수 있다. 풀이 자체는 매우 쉬운데, 실수오차를 잘 핸들링하는 것을 의도한 문제 같다.

 

D1. RPD and Rap Sheet (Easy Version)

Easy version의 k=2 조건에서는 bitwise XOR과 동일하다. 1부터 n-1까지 모두 한 번씩 시도해 볼 수 있다. xor은 교환법칙과 결합법칙이 성립하므로, 이전에 시도해 본 값을 모두 xor해서 들고 다니다가 현재 시도할 값과 xor해서 시도하면 된다.