Codeforces Round #787 div3

https://codeforces.com/contest/1675

 

 

A. Food for Animals

 

https://codeforces.com/contest/1675/problem/A

 

pet store에 dog food \( a \) 팩, cat food \( b \) 팩, universal food (suitable for both dogs and cats) \( c \) 팩이 있다.

 

Polycarp는 개 \( x \) 마리, 고양이 \( y \) 마리를 가지고 있다.

 

Polycarp가 모든 동물들을 위한 food를 살 수 있는가.

 

먹이는 최소 한 팩씩 동물들에게 제공되어야 한다.

 

 

\( x -= \min(a, x) \), \( y -= \min(b, y) \) 를 한 다음 \( x + y \leq c \)를 만족한다면 가능하다.

 

이외에는 불가능하다.

 

 

B. Make It Increasing

 

https://codeforces.com/contest/1675/problem/B

 

\( n \)개의 정수 sequence \( a_1, a_2, ..., a_n \)이 주어졌을 때, 다음과 같은 operation을 할 수 있다.

 

- \( a_i \) ( \(1 \leq i \leq n \) ) 을 선택하여 \( a_i = \lceil \frac{a_i}{2} \rceil \)로 만든다.

 

sequence를 strictly increasing ( \( a_1 < a_2 < ... < a_n \) ) 하게 만들기 위한 operation의 최소 횟수를 구하여라.

 

strictly increasing하게 만들지 못한다면 -1을 출력하여라.

 

 

greedy하게 접근하면 된다.

 

마지막 원소부터 순회하며 \( a_i \)가 0이 아닐 때, 앞의 원소보다 더 작아지도록 현재 원소에 operation을 반복하며 counting을 한다.

 

만약 \( a_i == a_{i + 1} \)인 경우 불가능하다.

 

이 외에는 가능하며 counting한 것을 출력한다.

 

 

C. Detective Task

 

https://codeforces.com/contest/1675/problem/C

 

Polycarp는 비싼 그림을 사서 \( n \)명의 친구들에게 보여주려고 한다.

 

방 하나에 그림을 걸어놓았으며 \( n \)명의 친구들이 한 명씩 순서대로 방에 입장해 그림을 감상한다.

 

모든 친구들에게 그림을 보여준 후 Polycarp는 자신의 그림이 사라진 것을 발견하였다.

 

Polycarp는 \( n \)명의 친구들에게 자신의 차례에 방 안에 들어갔을 때 그림이 있었는지를 물어보았다.

 

친구들은 있었다 / 없었다 / 기억하지 못한다로 답하였다.

 

범인 이외의 모든 사람들은 진실만 얘기하였다.

 

범인일 수 있는 사람들은 몇 명인지 구하여라.

 

 

\( i \)번째 사람이 범인인지 아닌지를 확인할 때 앞의 사람들은 있었다 / 기억하지 못한다로, 뒤에 사람들은 없었다 / 기억하지 못한다로 되어있으면 \( i \)번째 사람이 범인일 수 있다.

 

이를 부분합같은 것으로 계산하면 된다.

 

 

D. Vertical Paths

 

https://codeforces.com/contest/1675/problem/D

 

\( n \)개의 정점으로 이루어진 tree가 주어진다.

 

각각의 정점들은 1부터 \( n \)까지 numbering 되어있다.

 

다음과 같은 경로들의 set을 구하여라.

 

- 각각의 정점은 정확히 한 경로에 속해있어야 하고, 각각의 경로들은 하나 이상의 정점들로 이루어져 있다.

 

- 경로는 언제나 밑으로 내려가야 한다. (parent에서 son으로)

 

- 경로의 수는 최소여야 한다.

 

 

모든 leaf를 순회하며 다음과 같은 과정을 진행한다.

 

선택한 leaf에 대하여 계속해서 올라가는 경로를 구한다.

 

선택된 정점들은 사용하였다는 표시를 해준다.

 

올라가며 이미 사용하였던 정점들을 만나면 그 정점을 경로에 포함하지 않고 멈춘다.

 

올라갈 수 있을 만큼 끝까지 올라갔다면 경로를 뒤집어서 출력해준다.

 

 

 

E. Replace With the Previous, Minimize

 

https://codeforces.com/contest/1675/problem/E

 

알파벳 소문자로만 이루어진 문자열 \( s \)가 주어진다.

 

다음과 같은 operation을 사용할 수 있다.

 

- 문자열에 적어도 한 번 사용된 문자 하나를 선택하여 문자열에 있는 모든 그 특정 문자를 이전 알파벳으로 바꾼다.

('a'는 'z'로 바꿀 수 있다.)

 

\( k \)번 이하로 operation을 하여 문자열을 사전적으로 가장 앞서는 문자열로 바꾸어라.

 

 

앞에서부터 문자를 'a'에 가장 가깝도록 만드는 것이 가장 유리하다.

 

이를 잘 구현하면 된다.

 

 

F. Vlad and Unfinished Business

 

https://codeforces.com/contest/1675/problem/F

 

Vlad는 \( n \)개의 집과 \( n - 1 \)개의 길로 이루어진 도시에 살고 있다.

 

따라서 도시는 tree형태로 이루어져 있다.

 

한 길의 한쪽 끝에서 다른 쪽 끝으로 이동하는 것은 시간이 1분 걸린다.

 

Vlad는 index \( x \) 집에서 출발하여 \( k \)개의 집에 들린 후 index \( y \) 집에 도착하려 할 때 최소 시간을 구하여라.

 

\( k \)개의 집은 어떤 순서로 도착하던 상관없다.

 

 

index \( x \) 집을 root로 하는 tree를 재구성한다.

 

이때 모든 정점의 parent는 유일하게 결정된다.

 

이후 \( y \)에서 \( x \)로의 거리를 구한다.

 

이 때 경로에 속하는 모든 정점들은 방문한 것을 표시해준다.

 

그다음에는 \( k \)개의 집들을 순회하며 root 방향으로 정점들을 방문한다.

 

현 정점에서 이동할 다음 정점이 방문한 정점이라면 거기서 멈춘다.

 

이렇게 형성한 경로의 길이 * 2를 답에 더해준다.

 

 

G. Sorting Pancakes

 

https://codeforces.com/contest/1675/problem/G