Codeforces Round 892 (Div. 2)

8월 12일에 진행한 코드포스 892번 대회 일지입니다. 결론적으로 다시 퍼플이 되긴 했습니다. 이 굴레에서 언제쯤 빠져나갈 수 있을까요?

0:00~0:04

• A번 United We Stand을 잡았습니다.
• (가장 작은 수; 여러 개일 경우 모두)와 (나머지 수)로 나누면 됩니다.
• 나눌 수 없는 경우, 즉 (나머지 수)가 없는 경우 -1을 출력합니다.
• 발상에 3분 가량을 쓴 것으로 기억합니다.

0:04~0:15

• B번 Olya and Game with Arrays을 잡았습니다.
• 가장 작은 수를 잡아 나머지 배열의 가장 작은 수를 모두 그곳으로 몰면 됩니다. 즉 기본적으로 두 번째로 작은 수를 잡으면 됩니다.
• 발상에 5분 가량을 쓴 것으로 기억합니다. 한 번 틀렸습니다.

0:15~0:29

• C번 Another Permutation Problem을 잡았습니다.
• $(1, 2, …, r-1, r, n, n-1, …, n-r+2, n-r+1)$ 으로 수열을 잡으면 됩니다. 모든 경우의 수를 다 돌아볼 수 있습니다. 대회 당시에는 Proof by AC하긴 했는데, 어느 정도 자명하게 증명이 될 것이라 생각하기도 했습니다.
• 가장 큰 수가 제외되므로, 가장 큰 쪽의 숫자들은 크기가 비슷하고 그 외의 숫자들에서는 Greedy하게 최대를 끌어낸다는 생각으로 풀면 됩니다.
• 발상에 10분 가량을 쓴 것으로 기억합니다.

0:29~1:22

• D번 Andrey and Escape from Capygrad를 잡았습니다.
• 발상 0: 어떤 지점 $l$부터 $r$까지 포탈만을 이용해서 이동할 수 있다면, $l \leq x \leq r$인 모든 지점 $x$에서 $r$까지 이동할 수 있습니다.
• 발상 1: 맨 앞이 아닌 곳으로 가는 것은 의미가 없습니다. 어떤 포탈이 $(a,b)$의 출구를 가질 때, 포탈 내의 어떤 점 $x$에서 다른 포탈을 이용해 $y$까지$(b \leq y)$ 이동할 수 있다면, $b$에서도 $y$까지 이동할 수 있습니다.
  • 따라서, 우리는 두 변수 $l, b$만 사용하면 됩니다.
• 발상 2: 어떤 지점 $x$에서 그 어느 방법으로도 오른쪽으로 이동할 수 없는 경우, $x$ 왼쪽의 모든 점에 대해서 $x$보다 오른쪽으로 갈 수 없습니다.
• 발상 3: 두 포탈 $a, b$와 $c,d$가 $c \leq b$ 및 $a \leq d$를 만족한다면 두 포탈을 하나로 합칠 수 있습니다.
• 따라서, 포탈을 겨속 합쳐서 서로 독립적이고 선형적 위계를 가지는 여러 개의 포탈으로 합칠 수 있습니다. 이 과정은 구간 그래프를 채색하는 과정(= 강의실 배정의 priority_queue 풀이)과 비슷하게 할 수 있습니다.
• 라는 발상에 30분 이상을 투자했습니다.

1:22~2:00

• 잤습니다.

후기

PS 실력이 아직 안 죽은 것 같긴 한데, 빠른 발상 능력을 다시 재활해야 할 필요가 있습니다. :blobsad: 퍼플에 5번째로 왔습니다. 이게 맞나 싶습니다.