Pinely Round 3 (Div. 1 + Div. 2)

Dashboard - Pinely Round 3 (Div. 1 + Div. 2) - Codeforces

 

8개월 만에 코포를 쳤다. 지금껏 갖은 핑계를 대면서 복귀를 계속 미루고 미뤘었는데, 이제 진짜 레드 갈 때까지 멈추지 않는다. 개인적으로 조금의 운을 탄다면 레드를 갈 가능성이 있다고 보고 있고, 이번 방학 내에 달성하는 것이 목표긴 하다. 이번 컨테는 평타는 쳤지만 오랜만에 해서 그런지 미숙한 부분이 많아서 아쉬웠다.

 

Prob. A

잘 생각해보면 원점 기준 상하좌우로 모두 움직여야 한다면 불가능하고, 나머지는 가능하다.

 

Prob. B

자연스럽게 2로 나눈 나머지를 생각할 수 있고, 2로 나눈 나머지가 한 종류라면 4로 나눠보면 두 가지로 갈라질 수 있고, 그게 안 되면 8로 나눠보고, ... 를 반복하면 된다. 언젠가는 무조건 되는데, integer overflow를 고려했다고 생각했으나 사실 고려하지 못해서 한 번 틀리고 10분을 허비했다. 내 풀이가 틀린 줄 알고 상당히 당황했다.

 

Prob. C

이건 잘 모르겠다. 대충 $l$, $r$, $c$ 배열을 다 정렬하고 구간의 길이를 항상 짧게 매칭한 다음에 $c$하고 그리디하게 매칭하면 맞긴 하는데 정당성은 생각 안 해봤다. 잘못 매칭해서 2번 틀렸는데, 이건 오히려 정당성을 증명했다고 생각했어서 의문이다.

 

Prob. D

첫 번째 관찰은 수들이 서로 연산에 영향을 못 준다는 것이다. 두 번째 관찰은 $a_i$와 $k$의 대소관계가 중요하다는 것이다. 나중에 다 같아지는 수를 $x$라고 하자. $a_i < k$라면 $x < k$여야 하고, $a_i = k$라면 $x = k$여야 하고, $a_i > k$라면 $x > k$여야 한다. 왜인지는 잘 생각해보자. 그래서 모든 $a_i$와 $k$의 대소관계가 동일해야 한다. 동일하면 항상 가능한데, 이건 그냥 믿었다. 모든 $a_i$가 $k$보다 클 때만 풀어보자. 나머지도 사실상 같다. $a_i$를 $x$로 만드는 데에 필요한 연산 수를 $t_i$라 하면 $a_i + k \times t_i = x \times (1 + t_i)$가 성립해야 한다. 왜인지는 잘 생각해보자. 조금의 식 정리를 하면 $1 + t_i$가 $a_i - k$의 약수여야 하고, 따라서 $x$도 $a_i - k$의 약수여야 한다. 우리가 구하고자 하는 것은 $\sum t_i$의 최솟값이므로 $x$가 클수록 좋다. 따라서 $x$는 $gcd(a_i - k)$이고, 이때의 $\sum t_i$를 계산하면 된다.

 

Prob. E

모든 버튼을 누르면 약수가 홀수 개인 수, 즉 제곱수만 살아남는다. 그런데 제곱수의 개수는 매우 적어서 $N \geq 20$일 때는 다 이 방법으로 처리된다. 나머지는 완탐 비슷하게 하면 되는데, 너무 무지성으로 하면 안 되고 적당한 커팅이 필요하다.

 

Prob. F1

$a_i \le a_{i+1} \le a_i + 2$ 여야 한다는 관찰을 바탕으로 적당한 예외 처리를 해주고 $a_i$와 $a_{i+1}$의 차이에 따라 $dp$를 잘 해주면 된다. 근데 그게 자꾸 머릿속에서 꼬여서 구현을 하지 못했다. 쓰기 귀찮아서 글이 짧아짐...