Codeforces Round #782 (Div. 2)

언레로 치니까 괜히 더 잘 되는거 같다.

A. Red Versus Blue (0:02, +)

R/(B+1)개와 R/(B+1)+1개를 적절히 배치해주면 된다.

 

B. Bit Flipping (0:16, +)

앞에서부터 그리디하게 설정해주면 되는데.. 구현 미스가 나서 좀 오래 걸렸다. 

 

C. Line Empire (0:40, +)

끝 위치가 \(x\)라면, 그 전까지는 계속 옮겨주는 것이 최적이다. 이를 각 경우에 대해 계산해주면 된다.

 

D. Reverse Sort Sum (1:06, +)

우선 주어진 배열의 평균을 통해 1의 개수를 구해준다. 이후, 뒤 원소부터 보며 자명하게 결정 -> 1의 개수에 따라 업데이트를 반복해주면 문제를 해결할 수 있다. Range Update Point Query 펜윅트리를 사용하면 \(O(NlogN)\)에 문제를 해결할 수 있다.

 

E. AND-MEX Walk (1:58, +)

1과 2가 같은 집합에 등장할 수 없기 때문에, 답은 자명하게 0, 1, 2 중 하나이다.

0을 판별하는 것은 쉽다. 끝까지 켜져 있는 비트가 최소 하나는 있어야 하므로, 각 비트별로 켜져 있는 가중치의 간선만 적용하는 방법으로 이를 판별해줄 수 있다. 구현은 Union-Find를 이용한다.

어려운 부분은 1과 2를 구분하는 것이다. 답이 1이라는 것은, 집합의 마지막 원소가 0이며 1이 포함되지 않는다는 것이다. 이는 처음으로 짝수 가중치의 간선을 탈 때, 집합에 1이 등장하지 않았음과 동치이며, 이는 곧 짝수 가중치를 타기 전에는 0번째 비트에 더해서 추가적으로 하나의 비트가 켜져있어야 함을 의미한다.

따라서 이를 Union-Find를 통해 합쳐주되, 해당 Component에 짝수 간선이 연결되어 있는지를 판별해주면 문제를 해결할 수 있다. 시간 복잡도는 \(O(60N)\) 정도이다. Union-Find 구현에 따라 로그가 붙을 수도 있다.