Codeforces Round 896 (Div. 1)

2023년 9월 10일에 진행한 코드포스 896번 대회 일지입니다. 처음으로 Div. 1 독립 대회를 쳐봤는데, 개쩌는 운빨(과 실력 상승)으로 떡상했습니다. 요즘 기부니가 아주 좋습니다.

0:00~0:18

• A번을 잡았습니다.
• 행렬의 크기가 주어지면 (각 열의 MEX들)의 MEX를 최대로 하는 행렬을 구성하는 문제였습니다.
• 시도 1: $n > m$인 예제 한 가지를 시도했습니다: $n=5, m=3$. 이때는 {0, 1, 2}, {1, 2, 0} 두 가지를 번갈아 쓰면 MEX=3이 됩니다.
• 발상 1(~5분): $n>m$일 때 MEX값이 $m$이 되는 경우를 구성할 수 있는 일반적 방법을 찾았습니다.
• 시도 2: $n<m$인 예제 한 가지를 시도했습니다: $n=3,m=5$. 이때는 {0 1 2 3 4}, {1 2 3 4 0}, {2 3 4 0 1}의 세 행으로 채우면 MEX=4가 됩니다
• 발상 2(~10분): $n<m$일 때는 MEX값이 $n+1$이 되는 경우를 구성할 수 있는 일반적 방법을 찾았습니다.
• 발상 3(~13분): $n=m$일 때는 $n$이 1 작을 때를 채우고 마지막 열을 위의 열 중 하나로 채워 MEX값을 $n$으로 할 수 있습니다.
• 세 가지를 모두 담아 구현했고 맞았습니다.

0:18~0:46

• B1번을 잡았습니다.
• 발상 1(~4분): 그냥 주개와 받개를 일대일대응시키면 되지 않을까요?
  • 7분에 제출하여 WA on TC6을 받았습니다.
  • 반례를 찾았습니다: {1 7 7}
• 발상 2(~15분): 평균으로 가야 하므로, 평균까지의 차이를 구해 둡시다. 어떤 0 이상의 정수 $a, b$에 대해, 평균까지의 차이에서 에서 $2^a$를 더하고 $2^b$를 빼서 0을 만들 수 있어야 합니다. 모든 자연수에 대해 이러한 $a, b$를 고르는 경우의 수는 유일하거나 존재하지 않는데, 변환이 존재하지 않는 수가 있으면 불가능합니다. (이 사실은 B1에서만 사용할 수 있습니다.)
  • 0의 경우 아무 수나 서로 주고받거나 하는 식으로 해서 처리할 수 있습니다.
• 발상 3(~20분): 이렇게 하면 모든 수에 대해 ‘줄 수’와 ‘받을 수’가 정해집니다. 이들이 서로 일대일대응하게 하면 됩니다.
• 구현했고 맞았습니다.

0:46~1:18

• B2번을 잡았습니다.
• 발상 1(B1 풀이 중): B1과 B2의 다른 점은, 이제 $2^a$를 더하고 $2^b$를 뺄 수도 있지만 $2^a$를 더하기만 할 수도 있고 $2^b$를 빼기만 할 수도 있으며 둘 다 안 할 수도 있습니다.
• 발상 2(~3분): 이러한 차이점은 다음 경우에서만 유일합니다: 평균까지 차이가 $2^t$꼴인 수. 이러한 수의 경우, $2^t$를 빼주기만 할 수도 있고 $2^{t+1}$을 뺀 뒤 $2^t$를 더해줄 수도 있습니다(혹은 반대로 더하기만 하거나 더하고 뺄 수 있습니다)
• 발상 3(~7분): 발상 2의 작업이 가능한 경우, 일단 $2^t$를 대응시켜 보고 그게 안 되면 $2^{t+1}$을 뺀 뒤 $2^t$를 더하는 동작을 시도하도록 할 수 있으면 좋겠습니다. 이를 어떻게 만들 수 있을까요?
  • 발상 3-1: 차이가 $2^t$꼴인 수가 $r$개 있다면, 나이브로 모두 시도하는 것은 적어도 $O(2^r)$입니다. 따라서, 시도의 방향성이 있으면 좋겠습니다.
  • 발상 3-2: 가장 작은 수부터 하나씩 올라가면서 확인할 수 있는 방법을 고안할 수 있을까요?
• 발상 4(~20분): 줄 수와 받을 수는 모두 $2^n$꼴이므로, 로그를 씌운 뒤 배열 같은 것에 각각의 개수를 저장해 둡시다. 이때 $2^n$을 줄 수 있는 수의 개수를 $a_n$, 받을 수 있는 수의 개수를 $b_n$이라고 둡시다. (문제 1의 경우, 모든 $n$에 대해 $a_n=b_n$이면 되었습니다.) 이제 발상 2의 동작은 다음과 같은 동작으로 생각할 수 있습니다:
  • $a_n-=1, b_n+=1, a_{n+1}+=1$.
  • $a_n+=1, b_n-=1, b_{n+1}+=1$.
• 이 동작을 $a_n, b_n$에 가하면 $n-1$ 및 그보다 작은 수에 대해서는 영향이 없습니다. 따라서, $n=0$일 때부터 한 칸씩 올라가면서 위 동작을 이용해서 $a_n=b_n$이 되도록 만들어주면 됩니다.
• 구현했고 한 번에 맞았습니다.

1:18~1:55

• C번을 잡았습니다. 참고로 못 풀었습니다.
• 사실 문제를 보고 나서 별 생각을 안 하고 포기했습니다.
• 그래서 쓸 게 없습니다.

1:55~2:30

• 이 글의 앞부분을 작성했습니다.

후기

• 요즘 폼이 미쳤습니다. 실력인지 운인지 둘 다인지 뭔지 잘 모르겠습니다.
• 블루로 다시 떨어지지 말고 이대로 오렌지까지 쭉 올라가면 좋겠습니다. 언제쯤 오렌지에 갈 수 있을지는 잘 모르겠습니다.
• 처음 딥1이었는데(사실 노솔튀를 한 적이 한 번 있어서 두 번쨰 딥1이었습니다) 이 정도면 잘한 것 같습니다..?