2022-03-02 Codeforces Round #773 (Div. 1)

마지막 수정 시각: 2022-03-02 16:45:00

Performance: 2337

오랜만에 코드포스 연습을 다시 시작했다. 그래도 레드는 찍어보고 끝내고 싶어서, 매주 최소 한 번은 virtual 돌리면서 기록을 남기고 연습하고 할 생각. 과연 얼마나 갈 지는 모르겠으나...

초반 페이스는 괜찮았는데 C를 푸는 도중에 온갖 곳에서 연락이 와서(이사날이 얼마 안남아서 부동산이나 뭐 인터넷 연결이나 등등을 많이 신청했는데 이상하게 이런건 꼭 대회 치는 중간에 연락이 온다..) 집중력도 흐트러지고 시간도 오래걸리고 해서 마지막에 좀 망친 느낌이라 아쉽다. 제대로 쳤으면 레드 퍼포먼스를 받을 수 있었을까? 흠... 잘 모르겠다. 잘 쳤어도 뭐 퍼포먼스는 2300 후반이었을듯. C 아이디어 관찰을 좀 더 빨리 했어야했는데 막혀서 너무 시간을 오래 쓴 감이 있다.

A. Great Sequence

그리디하게 풀 수 있다. 크기 순으로 정렬하고 \( j < i \)면서 \(a_j \cdot x = a_i\) 인 매칭되지 않은 \(j\)가 있다면 \(a_i\)와 \(a_j\)를 매칭해주면 된다. set 등의 자료구조를 이용해서 \(O(NlogN)\)에 해결 가능.

B. Repetitions Decoding

우선 절대 불가능한 조건을 생각해보자. 홀수개 존재하는 수가 있는 경우, 어떻게 해도 만들 수가 없다. 새로 추가하는 것도 수를 짝수개만 추가하고, 같은 수열이 반복되는 형태로 수열을 쪼개야하는데 그러면 모든 수가 짝수개 존재해야만 하기 때문.

그렇다면 모든 수가 짝수개 존재한다면 항상 만들 수 있을까? 가능한 방법을 제시할 수 있고 그 방법을 그대로 구현하면 그게 곧 답이면서 증명이 된다.

우선 수열의 맨 첫번째 수 \(a_1\)과 같은 수가 나오는 위치를 \(a_i\)라고 하자. \(a_1\)부터 \(a_{i-1}\)까지의 수열과 \(a_i\)부터 \(a_{2i-1}\)까지를 주어진 연산을 이용해서 같게 만드는건 항상 가능하다.

이렇게 만들었다고 치면, \(a_1\)부터 \(a_{2i-1}\)까지는 없다고 치고 \(a_{2i}\)부터 동일한 문제를 반복해서 해결하게 된다. 이 때, 매번 수열의 길이가 최소 \(1\)만큼(\(a_1\)은 반드시 매칭돼서 사라지므로)은 줄어들고, 최악의 경우 매 스텝마다 \(n\)번 연산을 해야할 수 있다. 따라서, 대략 \(n^2\)번의 연산이면 항상 수열을 정해진 조건에 맞춰 구성할 수 있음을 알 수 있다. 구현은 조금 까다롭다.

C. Anonymity Is Important

괜히 BOJ 탐사 비슷하게 생겨서 그거 생각하다가 시간을 오히려 더 날렸다. 그냥 상관없이 생각하면 되는데...

주어진 쿼리에서 \(x = 1\)인 경우, \(l\)부터 \(r\)까지 구간에서 환자를 추가로 특정할 수 있는 경우는 딱 하나밖에 없다.

• \(l\)부터 \(r\)까지 구간에서 정확히 한 칸만 환자 여부가 밝혀지지 않았고, 나머지 칸은 전부 환자가 아닌 경우

이 조건을 만족하지 않으면 환자를 추가로 특정할 수 없다.

문제는 \(x = 1\)인 쿼리가 앞에서 주어진 다음 뒤에서 주어지는 \(x = 0\) 쿼리 때문에 앞의 쿼리에서 환자가 추가로 특정될 수 있다는 부분인데, 오프라인으로 처리를 하면 이걸 해결할 수 있다.

\(t_i\) 를 \(i\)번 환자가 특정된 시간

이라고 하자. 우선 \(x = 0\)인 쿼리만 전부 순회하면서 \(t_i\)값을 계산하고 나면, \(x = 1\)인 쿼리를 차례대로 돌면서 위 조건을 만족하는 최초 시기가 언제인지를 알 수 있다.

이제 해당 시기를 알아내고 나면 그 시간 값과 해당 칸이 환자인지 아닌지 여부를 바탕으로 문제를 해결할 수 있다. 위에서 주어진 모든 과정은 set 등의 자료구조를 이용해 전체 \(O((N+Q)logN)\) 시간에 수행할 수 있다.