CodeForces Round 963 - Div 2

https://codeforces.com/contest/1993

 

 

Performance Rating : 2800

 

A

주어진 $s$에서 'A', 'B', 'C', 'D'의 개수를 각각 세놓고 개수와 $n$중 최솟값을 더해주면 된다.

 

B

홀수가 존재하면 모두 홀수로 만들어야 한다는 것은 빠르게 알아차려서 짝수만 있으면 0을 출력해 주고 아니면 짝수의 개수를 출력하는 코드를 짰으나 예제가 안 나와서 다시 보니 작은 것에 더해준다는 것을 발견했다. 그래서 $a$를 정렬해 놓고 현재까지 만들어진 가장 큰 홀수보다 짝수이면서 더 큰 값이 나오면 답을 1 키워주는 코드를 짰지만 틀렸다. 틀리고 다시 생각해 보니 2번을 실행하는 것은 가장 큰 짝수에서 하면 나머지 짝수들은 모두 한 번에 합칠 수 있다는 것을 알게 되어 고쳤다.

 

C

시간이 $\mathrm{max}(a_i)$가 넘어가면 모든 라이트가 $2k$를 주기로 진동하게 된다는 것을 보았다. 이를 통해 $a_i$를 $2k$로 나눈 나머지가 중요할 것 같다는 생각을 했다. 그래서 $a_i$를 $2k$로 나눈 나머지를 저장해두고 가능한 시작 시간의 $2k$로 나눈 나머지들을 누적합을 통해 구한 뒤 저장해두고 가장 작은 값을 찾았다.

 

D

문제를 보면서 파라메트릭 서치를 활용해야 될 것 같은 느낌을 받았는데 어떻게 활용해야 할지 감이 잡히지 않았다. 15분 정도 고민을 하다가 $k$개씩 연속한 구간들을 최대한 많이 잡을 때 합의 최댓값을 dp를 활용해 구할 수 있다는 것을 떠올렸다. 파라메트릭 서치를 하면서 $mid$의 값보다 작은 값들에 1을 표시해 놓고 dp로 합의 최댓값을 구하면 중앙값으로 $mid$를 만들 수 있는지를 판단할 수 있겠다는 생각이 들어 파라메트릭 서치와 dp를 활용해 문제를 풀었다.

 

E

F1의 솔브수가 E에 비해 2배 정도 되길래 F1을 먼저 풀고 돌아왔다. 두 가지를 관찰했는데 각 행과 열로 선택할 수 있는 종류는 각각 $n+1$, $m+1$가지라는 것과 순서를 임의로 설정할 수 있다는 것이다. 열끼리의 차이들을 저장해 두고 외판원 순회를 풀듯 dp를 해주면 차이의 최솟값을 구할 수 있겠다는 생각을 했다. dp가 $O(n^22^n+m^22^m)$이고 행과 열을 선택할 수 있는 경우의 수가 $O(nm)$이므로 시간복잡도가 $O(nm(n^22^n+m^22^m))$이라서 시간초과가 났다.

 

F1

굳이 반전을 시킬 필요가 없다는 것을 알게 되었다. 자유롭게 이동을 하도록 두고 $x$좌표가 $2w$의 배수, $y$좌표가 $2h$의 배수가 되는 경우의 수를 구하면 된다는 것을 관찰했다. 그래서 첫 주기 때 $x$좌표 변화량, $y$좌표 변화량을 구하였다. 그리고 경우의 수를 구해야 하기 때문에 $x$좌표를 $2w$, $y$좌표를 $2h$로 나눈 나머지를 구하고 좌표별로 오게 되는 횟수를 map에 저장해 두었다. 이를 통해 $k$번의 반복에서 원점을 지나는 횟수를 $O(klogn)$으로 구할 수 있었다.