Codeforces Round 914 (Div. 2)

Codeforces Round 914 (Div. 2)에 참가했다.

요즘 시간대가 안 맞아서 참여하지 못했었는데, 1600점을 달성하겠다는 강한 의지를 가지고 드디어 참가했다.

이번에도 3솔따리인가 싶었는데 운 좋게 3솔은 면했다.

 

---

 

A - Forked!   (00:09)

 

변형 나이트가 $(a, b)$만큼의 칸을 움직일 수 있을 때, 이동 한 번으로 두 좌표에 모두 도달 가능한 칸의 개수를 세는 문제다.

 

map으로 구현했는데, $a = b$인 경우를 빼느라 구현하는데 시간이 오래 걸렸다.

 

 

B - Collecting Game   (00:19)

 

수들을 모두 최소 PQ에 넣고 하나씩 빼면서 해당 수로 가능한 최대 개수를 구해줬다.

 

 

C - Array Game   (00:31)

 

우선, $k \ge 3$인 경우에는 답이 무조건 0이다.

두 번의 연산으로 같은 수를 두 개 만들고 해당 수들을 골라주면 무조건 0이 되기 때문이다.

 

$k = 1$인 경우에는 $O(n^2)$에 모든 쌍들에 대한 차의 절댓값 중 최소를 구해줬다.

$k = 2$인 경우에는 위에서 나온 $n^2$가지 경우와 원래의 $n$가지 수에 대해 이분 탐색으로 최소를 구해줬다.

 

 

D1 - Set To Max (Easy Version)   (01:40)

D2 - Set To Max (Hard Version)   (01:43)

 

어떤 인덱스 $i$에 대해, $a_i > b_i$인 곳이 있다면 답은 "NO"이다.

그렇지 않은 경우만 생각해보자.

 

$a_i = b_i$로 만드는 것이 목적이다.

$l<i$이면서 $a_l = b_i$인 곳을 찾자.

모든 $i$에 대해서 아래 두 가지가 모두 성립해야 한다.

1. $l < j < i$인 $j$에 대해, $a_j > b_i$인 $j$가 있어서는 안 된다.

2. $l < j < i$인 $j$에 대해, $b_j < b_i$인 $j$가 있어서는 안 된다.

모두 성립한다면, $l \le j \le i$에 대해 $a_j = b_i$로 만들어준다.

성립하지 않는다면, $r>i$이면서 $a_r = b_i$인 곳을 찾고, 위 과정을 비슷하게 수행한다.

 

여전히 성립하지 않는다면, 답은 "NO"이다. 어떻게 하더라도 $a_i = b_i$로 만들 수 없기 때문이다.

 

위 작업을 임의의 순서대로 한다면, 테스트케이스 3을 통과할 수 없다. $b_i$가 작은 순서대로 위 과정을 수행해야 한다.

 

 

이것이 내 풀이였는데, 나는 이게 $O(N^2\log{N})$이라고 생각했다.

시간이 얼마 남지 않았고, $1 \le a_i, b_i \le N$ 이길래 혹시 몰라서 Hard version에도 제출했는데 accept를 받았다.

데이터가 부실한건가? 했는데 $N = 200\,000$인 케이스에서도 약 1300ms에 잘 돌아간다.

내 풀이에 대한 worst case가 없었나..?

 

 

E - Tree Queries

 

문제를 보자마자 도망갔다.

 

 

F - Beautiful Tree

 

BOJ에서 비슷하다고 느낀 문제를 봤었는데, 풀지 못했었다.

애초에 이게 더 상위버전 같은 느낌이 강하게 들어서 포기했다.

 

---

Rating

 

+135

1584 $\rightarrow$ 1719

 

드디어 블루에 왔다. 목표 점수까지 181점 남았는데, 올해 안에 도달할 수 있을까?