Educational Codeforces Round 168 (Rated for Div. 2)

 

 

 

컨디션이 좀 안 좋았는데, 콘까지 말아먹으니까, 기분도 안 좋아졌다. 지문을 잘못 읽은 게 제일 컸다. 거의 모든 지문을 잘못 읽었다.

 

A. Strong Password

일단, 문자열 어디에든 한 개를 삽입할 수 있다고 지문에 나와있지만, 진짜 지문을 날려 읽었다.

이 부분만 읽고, "아 맨 앞이나, 맨뒤 하나? 그냥 브루트 포스를 하라는 건가?"라고 접근했고, 정말 앞뒤에 한 개씩 붙이는 52시도 브루트포스를 구현했다.

 

당연히도, 틀렸고, 정말 당황해서, 지문 다시 읽고 제대로 풀었지만, 코딩미스를 한번 해서 2번 틀렸다.

 

B. Make Three Regions

인접한 행과 열 그리고 접근 가능하다면, 하나의 컴포넌트로 묵는다. 문제는 한 블록을 막을 수 있을 때, 컴포넌트가 총 3개 되는 그런 블록들을 찾으라고 되어있다.

 

정말 이 부분만 이해하고, 바로 코딩을 다시 들어갔다;;; 컴포넌트를 일단 카운팅 해서, 컴포넌트가 1, 2, 3개일 때를 케이스 워크 했다.

근데;; 컴포넌트가 2개 일 경우 정말 구현 난이도가 조금 복잡해진다. 컴포넌트가 2개일 경우, 한 블록으로 막았을 때, 한 개의 컴포넌트를 가를 수 있는 경우의 수가 있기 때문에, 정말... 골치 아팠다.

 

근데? 나는 A에서 이상한 짓하고, B는 구현이 복잡해서 생각을 정리 중인데, 벌써 B는 3000명이 풀었다.

속으로는 정말 머릿속에 물음표를 뛰우고 지문을 다시 읽어봤다.

 

아.. 컴포넌트가 무조건 한 개인 입력만이 주어지는구나... 바로 맞췄다.

 

C. Even Positions

이 문제도 삽질을 거하게 했다. 삽질이라기보다는 이번엔 관찰 방향을 잘못 집었다.

일단 그리디 하게 ')'을 배정할 수 있으면, 배정하자!!라고 생각했다. 당연히 맞는 생각인데, ')'를 배정할 수 있는지 아닌지 확인을 어떻게 해야 할지 뇌절이 왔다.

 

컨디션도 너무 안 좋아서 그냥 뇌가 하얗게 변해버렸다. 그렇게 그림 그려가며, 다양하게 시도 중이었다.

문득, 지문이 왜 홀수 칸만 비웠을까?라고 궁금해졌다. 당연히 정답은 홀수칸에 집중하면 쉽게 얻을 수 있었다.

 

짝수칸에 '('가 있다면 비용은 3이 추가되고, ')'가 있다면 정답은 1이 추가된다.

 

쉬운 방법은 정말 옆에 있다 항상..

 

D. Maximize the Root

그냥 이 문제는 발상을 떠올리기가 너무 어려웠다. 워낙 알고 있는 자료구조도 많고 난이도도 가늠이 안되니까 이게 뭐 어떤 식으로 접근해야 할지 너무 힘들었다.

 

처음엔 어떠한 노드 $a$ 가 있어, 그 노드가 루트노드까지 이어진 경로 중 한 노드에게 최대 $\big\lfloor \frac{a}{2} \big\rfloor$ 번 번호를 전달할 수 있다고 생각했다. 이렇게 생각하니까, 머리가 꼬여버려 가지고 또 하얗게 질려버렸다.

 

지금도 살짝 이해가 안 되긴 하는데, 이건 트리 dp적으로 생각해야 한다.

$dp[i]$ 를 $i$노드의 서브트리만 생각했을 때, 그 서브트리에 속한 노드들이 가질 수 있는 가중치중 최솟값을 최대로 한 값이라고 하자.

 

어떠한 노드 $v$가 있어, 자식 노드들의 집합을 $\mathbb{V}$ 라고 하자. 결국 여러 자식들 가운데 최적화 된 정답을 도출하는 데 사용되는 값은 가장 작은 값이다. 이 값을 $F$ 라고 해보자. $v$의 가중치를 $W[v]$라고 하겠다.

$$F_v = \min_{i \in \mathbb{V}}(dp[i])$$

$$dp[i] = \begin{cases} 
\bigg\lfloor \frac{W[i] + F_i}{2} \bigg\rfloor & \text{if} \quad W[i] < F_i \\
F_i & \text{else}
\end{cases} $$

$$\text{Answer is} \; F_1 + W[1] $$

 

더 큰 값이 있어봤자, 어차피 다른 자식에서 먼저 값이 떨어지면 사용하지 못하기 때문이다.

 

E. Level Up

이건 그냥 보자마자, 자료구조 쓰는 거구나라고 알았다. 백준에서 자료구조를 그렇게 많이 풀었는데... 당연하다..

근데 시간이 얼마 남지 않아서, 그냥 포기했다.

 

$K$가 더 클 때, 탈주한 몬스터들은 $K$가 더 작아지면 당연히 또 탈주한다. 이 관찰을 하고 쿼리 거꾸로 정렬하고 $ K = N$부터 1까지 내려가면서 풀면 된다.

 

탈주한 하지 않은 몬스터들만 데리고 열심히 확인 해보면 된다.

구간 $[idx, \infty)$ 까지의 몬스터 들중, level 이하인 몬스터를 싹 제거한다.

그리고 level++, $idx= idx + K$ 해주면 된다. 계속 반복하면 된다.

 

추후에, 풀어봤는데, 어차피 틀린 문제였다고 생각한다. 스플레이 트리로 대충 긁었다.

$O(N log^2 N)$ 정도 나온다고 생각한다.

 

 

몸이 안 좋아도 코포는 그래도 꼭 한다. 떨어질 것 같아도 한다. 결국엔 많은 경험이 필요하다고 생각한다.