Codeforces Global Round 22

팀 연습이 끝나고 Rated 코포가 있길래 오랜만에 쳤다.

 

A. Glory Addicts (0:06, +)

잘 번갈아서 하는 것이 최적이다. 정렬한 후 큰 것 부터 써주면 되는데, A번 치고 케이스 워크가 좀 있는 편이라 어려웠다.

 

B. Prefix Sum Addicts (0:14, +)

\(N=K\)일 때는 배열을 만들 수 있으므로 단조증가인지 판별하면 되고, \(K=1\)일 때는 항상 가능하다.이를 잘 접목하면 그렇지 않은 상황에서도 만들어진 배열이 단조증가인지 판별하고, 만들어진 배열의 첫 항을 잘 만들 수 있는지 판별하면 된다는 사실을 알 수 있다.

 

C. Even Number Addicts (0:38, +1)

수가 무엇인지는 중요하지 않고 홀짝성만이 중요하다. 제한이 작으므로 홀수의 개수와 짝수의 개수, 누구의 턴인지.. 등을 인자로 하는 DP를 사용하면 해결할 수 있다. 나는 좀 더럽게 풀었다.

 

D. Permutation Addicts (1:05, +1)

문제에서 뭘 하라는건지 직관적으로 이해가 힘들었지만, 이해만 하면 꽤 쉽게 해결할 수 있다. 0 또는 \(n+1\)은 둘 중 반드시 한 종류만 등장하며, 이를 시작으로 잘 이어나가주면 된다.

 

E. Balance Addicts (2:23, +2)

0이 없다면 투 포인터 비슷하게 잘 나눠준 후 쉽게 해결할 수 있다. 0이 문제인데, 0이 \(a\)개, 1, 0이 \(b\)개 있는 상황의 경우의 수가 \( {a+b \choose a} \)라는 것은 식을 잘 정리하다 보면 알 수 있다. 이러한 segment가 여러 개 있으면 어려워지는데, 나는 브루트 포스 코드를 짠 후 대략적으로 때려맞췄다. 그럼에도 구현할 부분이 꽤 많기에 대회 종료 직전에야 해결할 수 있었다.. F도 푼 사람이 꽤 많았기에 아쉬웠다.