Hello 2023

Dashboard - Hello 2023 - Codeforces

A - Hall of Fame

L과 R이 각각 한 번 이상 등장해야 한다.

00:04 AC

 

B - MKnez's ConstructiveForces Task

if N == 3 then

    impossible :(

elif N % 2 == 0 then

    repeat 1 and -1

else

    repeat (N / 2 - 1) and (-N / 2)

00:16 AC

 

C - Least Prefix Sum

K > M인 경우와 K < M인 경우로 나누어서 보면 된다.

우선 S[i] = sum(A[1 .. i])로 정의하자.

 

K > M이고 S[K] < S[M]인 K가 존재한다면 연산이 필요하다.

조건을 만족하는 K가 여러 개라면 그중 최솟값을 선택한다.

이제 A[(M + 1) .. K] 중 최솟값인 원소에 대하여 연산을 수행한다.

조건을 만족하는 K가 존재하지 않을 때까지 이 작업을 반복한다.

 

구체적인 구현 방법은 다음과 같다.

K에 대하여 연산을 수행하면 M <= i <= K인 i에 대해서는 S[i] >= S[M]을 만족하게 된다.

따라서 i를 증가시키면서 S[i] >= S[M]을 만족하는지 확인하면 된다.

S[i] < S[M]이라면 연산을 수행해야 하는데 이때 최솟값은 priority queue로 구할 수 있다.

 

K < M인 경우도 유사하게 처리하면 된다.

00:36 WA

인덱스 1에 연산을 수행하는 것은 무의미하므로 인덱스 1은 무시해야 한다.

00:40 AC

 

D - Boris and His Amazing Haircut

우선 A[i] < B[i]인 i가 존재하면 답은 NO가 된다.

그렇지 않다면 size가 큰 razor부터 차례대로 사용하면 된다.

다양한 자료 구조로 풀이할 수 있는데 stack 풀이가 가장 간단해 보인다.

워낙 전형적인 문제라서 구체적인 풀이는 언급하지 않으려고 한다.

 

문제를 보자마자 풀이가 보였고 코딩도 금방 마쳤다.

그런데 예제가 나오지 않았다.

20분 정도 디버깅 하다가 사소한 오류를 범한 것을 발견하였다.

01:15 AC

지금까지 코포 하면서 예제를 7개 주는 문제는 처음 봤다.

예제 없었으면 무한 WA로 페널티 낭낭하게 쌓아서 레이팅 나락 갔을 것이다.

 

F - Xorcerer's Stones

서브트리의 크기가 짝수일 때 연산을 두 번 수행하면 서브트리 내의 모든 노드는 0이 된다.

이를 이용하면 약간 복잡한 트리 dp가 가능해진다.

02:21 AC

sequence를 구하는 과정이 조금 많이 까다로웠다.

 

E - Anya's Simultaneous Exhibition (not solved)

주어지는 그래프를 scc로 묶고 위상 정렬을 해보자.

이때 첫 번째 scc에 속하는 선수들만이 candidate master(이하 CM)가 된다.

하지만 주어지는 정보로 실제 그래프를 구축하기는 어려워 보인다.

문제를 해결하기 위해서는 두 가지 관찰이 필요하다.

 

첫 번째 관찰은 다음과 같다.

• out-degree가 가장 큰 선수는 반드시 첫 번째 scc에 속한다.

이는 귀류법을 이용하여 증명할 수 있다.

 

두 번째 관찰은 다음과 같다.

• 첫 번째 scc의 크기를 sz라고 하자.
• 이때 첫 번째 scc의 out-degree의 합은 sz * (2 * N - sz - 1) / 2가 된다.

증명은 간단하므로 생략한다.

 

위의 정보를 이용하면 다음과 같이 문제를 해결할 수 있다.

먼저 N번의 query로 각 선수의 out-degree를 구하고 out-degree의 내림차순으로 선수들을 정렬하자.

그리고 첫 번째 scc를 나타내는 집합 S를 공집합으로 초기화하자.

이제 sum(out-degree) = sz * (2 * N - sz - 1) / 2를 만족할 때까지 선수들을 S에 순차적으로 추가하면 된다.

S에 속한 선수들은 첫 번째 scc에 속하게 되므로 이들이 곧 CM이 된다.

 

G - The Game of the Century (not solved)

Pass

 

H - Olympic Team Building (not solved)

Pass

 

끝

끝