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