Codeforces Round 866 (Div. 1, Div.2)

https://codeforces.com/contest/1819

카페인을 먹으면 침착함이 좀 필요한 그래프 문제는 잘 못 푸는 것 같다.

이번에 3솔을 했다 (사실 B는 uphack 당해서 2솔이지만 내 레이팅은 올랐으니)

A랑 B를 상당히 빨리, 패널티 없이 풀어서 점수를 잘 먹을 수 있었다.

끝나기 5분전에 C를 AC 받았음에도 불구하고 내 최종 순위가 114등인 것 보니 다들 패널티로 애 좀 먹었을 것 같다.

그리고 이번에 D가 상당히 많이 터졌다. 거의 1/3정도가 TLE 맞았는데 그래서 더 퍼포가 잘 뜬 것 같다.

 

대부분의 사람은 1E, 1F를 못 풀기에 (실제로 대회중에 각각 8명, 0명이 품) div2 기준으로 문제 번호 기입.

 

C. Constructive problem

 

Mex값을 1 늘리는지 확인하는 것이다. 그러면 적당한 수들을 Mex로 바꿔주어야 한다.

1. 당연히 Mex = n이면 더 늘릴 수 없다.

2. Mex + 1이 없다면 무조건 가능하다.

3. Mex + 1이 있다면 무조건 제거해야 한다. (Mex + 2가 되기에)

-> 따라서 Mex + 1이 있다면 제일 앞의 Mex + 1부터 제일 뒤의 Mex + 1까지의 숫자를 모두 Mex로 바꿔주면 된다.

-> 바뀐 수열에 대해서 실제로 Mex + 1이 되었는지 확인해주면 끝.

 

D. The Butcher (uphacked.)

 

틀린풀이)

일단 맨 처음에 rectangle을 자르면 걔는 h나 w를 변의 길이로 가질 것이다. -> 두 가지 케이스

그냥 h를 변의 길이로 가진다고 하자.

그렇다면 h는 모든 a의 값들 중에서 최댓값일 것이다. (h = Max(a))

그리고 h를 변의 길이로 가지는 모든 사각형은 h, w에서 바로 잘려서 나온 애들일 것이다.

h를 변의길이로 가지지 않는 사각형들 중에서는 w를 변으로 가진 애가 있을 것이다. (w = Max(b))

마지막 안전빵으로 모든 넓이의 합이 h * w가 되는지 확인해준다.

 

아마 위의 풀이가 h, w를 구하는 과정까지는 맞을 것이다.

다만 실제로 h, w가 가능한지를 확인하는 과정이 더 필요할 것이다.

아마도 순차적으로 rectangle들을 set등에 넣어둔 뒤 한 변이 h, w, h', w'...을 순차적으로 지워나가면 될 것이다.

(아직 공식 editorial이 아직 안 나왔기에 더 이쁜 풀이가 있을지도 모른다)

 

E. The Fox and the Complete Tree Traversal

 

어떤 점 X가 있고 이의 Parent인 P, 그리고 child들인 c[0], c[1]...이 있다고 하자.

만일 P를 거쳐서 X로 들어간다고 생각하자.

X의 child들을 어떻게 잘 방문하였다고 하더라도 P와 X를 이미 방문하였기에 마지막에 P를 방문하며 끝나야 한다.

따라서 P를 거친 다음에 P에서 끝낼 생각이 아니라면 반드시 X를 건너뛰고 방문하여야 한다.

 

그렇다면 P에서 아래쪽으로 들어가면 X를 마지막으로 거치면서 나와야 한다.

P의 다른 child들 Y, Z, W...가 있다고 생각해보자.

그러면 X를 방문한 뒤에는 Y -> Z -> W ...를 방문하여야 하며 이들은 모두 leaf여야 한다.

만약 Y가 leaf가 아니라면 Y를 방문하여 들어갔으므로 반드시 P로 도달하고, P를 두 번 방문하니 순회는 끝이 난다.

즉 P가 순회의 시작이자 끝인 한가지 경우에는 leaf가 아닌게 하나까지는 더 있어도 괜찮다.

 

따라서 

1) 만약에 x를 건너뛰고 내 child들로 들어간다면

-> x의 child들 중 leaf를 모두 방문 -> 마지막으로 leaf가 아닌 애를 방문 -> x의 parent로 이동 ->...

2) 만일 x를 반드시 방문했다면

-> leaf가 아닌 child y를 건너뛰고 y의 child들을 방문 -> y를 방문 -> leaf인 child를 방문 -> x의 parent로 이동

-> 만일 x가 순회의 끝이여도 된다면 leaf인 child들을 모두 방문 -> leaf 아닌 child 하나 더 방문 -> x로 이동

 

leaf가 아닌 child가 두 개 이상 있어도 괜찮은 애는 root뿐이다. 

따라서 root를 leaf가 아닌 child가 두 개 이상 있는 노드로 미리 설정을 해두자.

순회결과의 길이가 N이면 Yes, 아니면 no