Codeforces Round 866 (Div. 1)

Dashboard - Codeforces Round 866 (Div. 1) - Codeforces

A - Constructive Problem

현재 mex를 x라고 하자.

x = N이라면 답은 No가 된다.

그렇지 않다면 배열 A에 (x + 1)이 존재하는지 확인한다.

(x + 1)이 존재하지 않는다면 답은 Yes가 된다.

 

(x + 1)이 존재하는 경우 A[i] = (x + 1)을 만족하는 i의 최솟값과 최댓값을 각각 l과 r이라고 하자.

A[l .. r]에 x를 할당하였을 때 mex가 (x + 1)이 되는지 확인하면 된다.

00:07 AC

 

B - The Butcher

h = max(a) or w = max(b)를 만족하여야 한다.

따라서 가능한 (h, w)는 최대 두 가지이다.

실제로 가능한지는 multiset<ii> 2개로 시뮬레이션 해보면 된다.

00:32 AC

 

C - The Fox and the Complete Tree Traversal (not solved)

주어진 트리가 이미지와 같은 서브그래프를 포함하지 않아야 한다.

트리의 지름을 이용하면 쉽게 구현할 수 있다.

대회 중에 정해와 유사한 접근을 시도하였으나 확신이 서지 않았고 반례가 있다고 생각하였다.

아직 수련이 부족하다.

 

D - Misha and Apples (not solved)

갓인타가 시스텟 터진 문제를 업솔빙할 이유가 없다.

Pass

 

E - Roads in E City (not solved)

Pass

 

F - Willy-nilly, Crack, Into Release! (not solved)

Pass

 

끝

끝