Codeforces Round 910 (Div. 2)

2023년 11월 20일에 진행한 코드포스 910번 대회 일지입니다. 적당히 빠른 4솔을 했고 오렌지 초중반대 퍼포가 나와서 올해 nm번째 퍼플에 왔습니다.

0:00~0:03

• A번을 잡았습니다.
• 시키는 대로 하되 맨 앞에서부터 바꿔주면 됩니다.
• 구현했고 맞았습니다.

0:03~0:10

• B번을 잡았습니다.
• 발상 1(2분): 뒤에서부터 보면 됩니다. 어떤 수가 그 직후의 수에 의해 조건을 만족하지 않는다면 만족하도록 최소한의 수로 나누어주면 됩니다. 이것을 맨 뒤의 수를 제외하고 모두에 대해 반복합니다.
• 구현했고 맞았습니다.

0:10~0:14

• C번을 잡았습니다.
• 무슨 소린지 이해를 못했습니다.
• D가 더 많이 풀렸다는 소리를 듣고 D를 잡으러 갔습니다.

0:14~0:38

• D번을 잡았습니다.
• 발상 1(5분): 숫자가 작은 게 묶여있는 곳과 큰 게 묶여있는 곳을 swap하는 것이 좋습니다.
• 발상 2(~10분): 식으로 작성해봅시다: $a_i$에 $a, b$가 있고, 그에 대응하는 $b_i$에 $a+x,b-y$가 있다고 합시다. 이 둘을 바꾸어 이끌어낼 수 있는 차이는 $abs(2b-2a-x-y) - (x+y)$입니다. (단 $x,y \geq 0$)
• 발상 3(~16분): 이는 $a_i+b_i-abs(a_i-b_i)$ 중 최대에서 $a_i+b_i+abs(a_i-b_i)$중 최소를 빼는 것과 동치입니다. 따라서, (값을 바꾸지 않는 행동이 가능하다는 것을 유념해야 합니다,) 식은 다음과 같습니다.
  • 원래 식의 beauty값 $k$, $a_i+b_i-abs(a_i-b_i)$의 최댓값 $x$, $a_i+b_i+abs(a_i-b_i)$의 최솟값 $y$에 대해, $k+max(0,x-y)$
• 구현했고 맞았습니다.

0:38~1:12

• C번으로 돌아왔습니다. 문제를 이해했습니다.
• 발상 1(3분): 최단거리와 같은 기우성을 가지고 최단거리보다 긴 경로는 모두 가능합니다.
  • 그렇지 않은 경로에 대해서는 NO를 출력합니다.
  • 가능하다면, 그냥 왼쪽과 아래 벽면을 따라서 이동할 수 있도록 alternating colored path를 만들어줍니다. 그리고, +2k의 길이의 path를 사용할 수 있도록 왼쪽 아래 꼭지점을 주변으로 무한히 머무를 수 있는 cycle을 만들었습니다.
• 구현했고 subtask 1에서 틀렸습니다.
• 발상 2(20분): 위 발상은 +4k의 길이만을 사용할 수 있음을 보장합니다. 따라서, 길이 +2를 사용할 수 있도록 해야 합니다. 이는 경로의 임의의 부분에 ㄷ자 경로를 만들어 해결할 수 있습니다.
  • 간단하게 (1,1)에 만들었습니다.
• 구현했고 맞았습니다.

1:12~1:40

• E번을 잡았습니다.
• 생각을 하지 못했습니다.

1:40~2:00

• 실시간으로 퍼포가 떨어지는 것을 구경하며 퍼플에 갈 수 있을지 아닐지 지켜봤습니다.
• 간발의 차로 1903(+93)을 달성하며 퍼플에 왔습니다.

후기

• CD 배점이 둘 다 1750이라, 두 개만 적당히 빠르게 풀어내면 오르겠다고 생각했습니다. 실제로 그렇게 되어서 다행이었습니다.
• 다만 C, D 모두 시간을 조금 너무 많이 쓴 것 같습니다. 특히 C는 발상 1과 2 사이에서 너무 오래 갇혀 있었습니다.