Educational Codeforces Round 132 (Rated for Div. 2)

오랜만에 언레로 치는 Div. 2이다. 언레라 좀 중간중간 놀면서 쳤다..

 

A. Three Doors (0:04, +)

경우를 잘 나누어주자.

 

B. Also Try Minecraft (0:12, +)

양 방향으로의 누적합 배열을 만들어주면 쉽게 해결할 수 있다.

 

C. Recover an RBS (0:20, +)

만약 만드는 방법이 유일하다면 ?인 자리에 대해서 (((..))) 형태일 것이다. 괄호 문자열의 조건 상, 가장 안전한 다음 해는 (((..)(..)) 형태일 것이기 때문에 이 형태의 해를 만든 후 괄호 문자열인지 판별해 주면 된다. 인덱싱 실수로 한 번 틀렸다.

 

D. Rororobot (0:31, +)

만약 x좌표의 차이나 y좌표의 차이가 k로 나누어떨어지지 않으면 불가능하다. 이 조건을 통과한 경우, 최적해가 아닌 가능 여부만 알아보면 되므로 위로 쭉 가서 이동하는 것이 최적이다. 따라서 가능한 위로 간 좌표를 구한 후 최댓값 세그먼트 트리 등을 이용해 해당 좌표를 넘는 벽이 있는지 판별해주면 된다. 

 

E. XOR Trees (1:47, +5)

만약 어떤 경로가 있다면, 경로에 속한 정점 중 하나를 \(2^{30}\)이 넘는 수로 바꿔주면 해당 정점을 지나는 경로들은 모두 XOR이 0 이상이다. 따라서, 이 문제는 경로의 XOR 값이 0인 모든 경로를 덮을 수 있는 최소 개수의 정점 집합의 크기를 고르는 문제가 된다. 여기서 한 가지 관찰을 할 수 있다: 트리를 루트 있는 트리로 간주했을 때, 경로가 발견될 때마다 지워주는 것이 최적이다. 경로가 발견되는 정점은 해당 경로에 속한 정점 중 가장 높은 정점일 것이며, 이 정점을 놓치면 경로를 지울 수 없기 때문이다. 경로의 XOR이 0인지 판별하는 것은 각 정점에 대해 루트부터의 경로 XOR값을 저장해주는 것으로 해결할 수 있으며, 이를 저장해주는 것은 Small to Large를 이용하면 된다. 말도 안되는 제출을 몇 번 해서 좀 많이 틀렸다.