CodeForces Round 1014 - Div 2

https://codeforces.com/contest/2092

 

 

Performance Rating : 2400

 

A

유클리드 호제법에서 $gcd(a, b)$의 최댓값은 $|a-b|$이므로 $a_i$에서 최댓값과 최솟값의 차이가 답이라는 생각으로 풀었다.

 

B

문제를 잘못 읽고 $a$와 $b$를 같게 만들 수 있는지를 출력해서 틀렸다. 결국 서로 바꿀 수 있는 위치들이 정해져 있으므로 $a_{2i}$, $b_{2j+1}$에서 $0$의 개수와 $a_{2i+1}$, $b_{2j}$에서 $0$의 개수를 각각 세어 두고 각각의 개수가 $n/2$, $(n+1)/2$이상인지 확인했다.

 

C

모든 숫자가 짝수 또는 홀수라면 시행을 할 수 없으므로 최댓값을 출력했다. 이제 짝수와 홀수가 각각 하나 이상씩 존재하는 경우에 대해 생각을 해보았는데, 짝수는 모두 흡수될 수 있으나 홀수의 경우에는 하나를 제외하면 모두 $1$이 남는 것을 확인했고 모든 $a_i$의 합에서 홀수의 개수 -1을 빼서 답을 구했다.

 

D

'L', 'I', 'T'의 개수를 각각 세고 가장 작은 것의 개수를 두 번째로 작은 것의 개수와 같도록 맞추면 가장 큰 것의 개수와 같도록 맞추는 것은 가장 개수가 많은 것을 제외한 두 문자를 하나씩 넣어주는 것으로 해결된다는 것을 관찰했다. 가장 개수가 적은 것을 다른 하나와 개수가 같도록 맞춰주는 과정을 구현하는데 실수를 한번 했고 어떤 것의 개수가 가장 작은지에 따라 casework를 하느라 코드의 길이가 300줄 이상 나왔다. 이런 문제에서 구현을 간단하게 하는 법을 jinagly님의 코드를 보고 배웠다.

 

E

$n$과 $m$의 크기가 매우 큰 것을 보고 조건을 간단하게 만들 방법이 있다는 것을 눈치챘다. 관찰을 해보다가 꼭지점이 아닌 모서리에 접하는 cell 중 검은색 cell의 개수가 홀수이면 인접한 cell 중 색이 다른 쌍의 개수가 홀수가 나올 것 같다는 생각이 들었다. 인접한 cell 중 색이 서로 다른 쌍의 개수가 연결 요쇼의 둘레와 연관이 있을 것 같아 그런 생각을 했고 엄밀한 증명은 하지 않았다. 모든 모서리의 색이 다 지정되어 있는 경우에는 모서리 중 검은색의 개수가 홀수라면 답은 $0$이 되고, 짝수라면 답은 $2^{nm-k}$가 된다. 모서리의 색이 다 지정되지 않은 경우에는 답이 $2^{nm-k-1}$이 된다.