Codeforces Round 920 (Div. 3)

 

 

Round 917에서 내 실력에 허무함을 느끼고 한동안 PS를 하지 않았었다.

그러다 블루 복귀를 위해 간절함을 가지고 다시 시작하게 되었다.

 

---

A - Square   (00:02)

네 개의 점이 사각형을 이루는 것이 보장되므로 네 점에 대한 $x$, $y$좌표의 최소, 최댓값을 구해 놓으면 넓이를 구할 수 있다.

 

 

B - Arranging Cats   (00:08)

두 수열에 대해 같은 인덱스끼리 xor을 해주고 다시 저장하면, 변화를 줘야 하는 박스들만 남는다.

두 수열에서 남은 $1$의 수 중 최댓값 만큼의 작업으로 두 수열을 같게 만들 수 있다.

 

 

C - Sending Messages   (00:16)

$m_i$에서 $m_{i+1}$로 갈 때, 폰을 껐다가 다시 키는 경우와 쭉 켜두는 경우 중 더 작은 값에 해당하는 경우를 선택하면 된다.

 

 

D - Very Different Array   (00:35)

두 수열을 정렬한 뒤에 생각해도 문제는 변하지 않는다.
수열 $a$에 존재하는 원소들은 반드시 $b$의 원소 중 하나와 매칭되어야 한다.
이 때, 정렬된 수열 $b$에서 $b_i$가 아직 매칭되지 않았는데 $b_{i+1}$이 매칭될 수는 없다. ($b_{i+2}$도 아직 매칭되지 않았다고 가정)
이러한 사실을 바탕으로, $b$에서 선택되는 원소들은 반드시 $b_1$ ~ $b_i$, $b_j$ ~ $b_m$이 되어야 함을 알 수 있다.
$i, j$를 고르는 경우는 $N+1$가지이고, 처음에 한 가지 경우에 대해서만 미리 값을 구해놓으면 포인터 하나를 옮겨가며 나머지 경우들도 구할 수 있다.

 

 

E - Eat the Chip   (01:06)

초기에, 두 말이 떨어진 행의 차이가 홀수라면 선공이 상대를 쫓아가야 하고, 짝수라면 선공이 상대로부터 도망가야 한다.이 사실을 판단해놓고, 시뮬레이션을 돌리면 된다.

 

 

F - Sum of Progression

처음 보는 유형의 쿼리 문제였다.원소가 변하는 쿼리가 없는 걸로 봐서 전처리를 잘 해놓으면 구하는 방법이 있겠다 싶었는데, 찾지 못했다.

 

 

G - Mischievous Shooter

???

 

---

Rating

+74

1557 $\rightarrow$ 1631

 

다시 블루로 복귀했다. 지금까지의 실력을 보아하니, 퍼플까지는 시간이 좀 걸릴 것 같다. 더 열심히 공부하고 도전해야겠다.