Codeforces Round #738 후기

-56 gg

 

구현이 정확한 건 너무 좋았는데 전혀 빠르지 않았다.

D1의 핵심적 관찰을 해놓고도 기초가 없어서 못 푼건 좀 아프다.

 

A. Mocha and Math

시행을 하면 할수록 값들이 작아진다. 따라서 그냥 모든 쌍에 대해서 한번씩 시행해주면 된다.

 

B. Mocha and Red and Blue

연속된 ?들의 색을 번갈아 칠하는데, 연속된 ? 앞의 문자와 다른 문자로 시작해서 번갈아 칠하면 된다.

이 전략대로 칠하면 연속된 색이 1개 이하로 추가된다. 따라서 중간에 연속된 것이 존재하는 해는 무의미하다.

 

C. Mocha and Hiking

예제를 가지고 놀다 보면 가능한 경로가 몇 개 없다는 걸 알게 된다.

1. n+1 -> 1 -> .. -> n 경로

2. 1 -> .. -> n -> n+1 경로

3. 1 -> .. -> k -> n+1 -> k+1 -> .. -> n 경로

 

1번은 n+1 -> 1 경로가 존재하면 가능하고

2번은 n->n+1 경로가 존재하면 가능하고

3번은 k->n+1, n+1->k+1 경로가 동시에 존재하면 가능하다.

 

이게 무슨 토너먼트 그래프랑 관련이 있다는데 엄청 고인물들은 잘 아는 거 같다.

 

D1. Mocha and Diana

1. 예제를 갖고 놀다 보면 한쪽 트리는 반드시 완성시킬 수 있을 거 같다는 느낌이 든다.

2. 이는 놀랍게도 참이며, 심지어 그냥 한쪽 트리를 완성시킨다는 마인드로 모든 간선을 적당히 추가하다 보면 답이 나온다.

 

1번은 찾았는데 트리를 완성시킬 때 유니온 파인드를 쓴다는 기본적인 감각조차 없어서 망했고..

2번 추측까지 갈 정도로 과감하진 못해서 망했다.

 

내 실력이 처참하다는걸 다시금 느낀다!