Codeforces Round 915 (Div. 2)

Posted Dec 17, 2023 Updated Dec 17, 2023

By 7 min read

2023년 12월 16일에 진행한 코드포스 915번 대회 일지입니다. 시험기간 버프로 역대급으로 잘한 것 같습니다만 약간 후회도 됩니다.

0:00~0:01

B번을 잡았습니다.
발상 1(1분): 긴 직선을 잘 뽑으면 다 루트로 갈 것 같이 생겼습니다.
발상 2(2분): 리프 노드 두 개를 골라 줄이면 두 리프가 루트로 없어집니다. 따라서 리프 노드의 수를 $x$라 할 때 $[\frac{x+1}{2}]$이 답입니다.
구현했고 맞았습니다(3분).

C번을 잡았습니다.
Largest Subsequence를 편의상 LS라 부르겠습니다.
발상 1(3분): LS를 찾아서 줄이기 시작하면 그 LS의 모든 원소가 정렬됩니다. 이러한 동작을 반복함을 통해 답을 구할 수 있을까요?
직관: LS를 찾는 연산이 여러 번 필요한 것이 맞을까요? 아마 LS를 한 번만 찾아도 정렬된다던가 하는 것이 있을 것 같습니다.
발상 2(8분): 직관이 맞았습니다. 한 LS를 줄여서 끝내 놓으면 다음 LS를 찾아 줄인다는 것은 없습니다. 따라서, LS를 정렬한 것이 전체 문제열을 정렬한 것과 같다면 (LS의 길이 - 1)이 답이 되고 아니면 -1이 답입니다.
구현했고 WA on TC2가 나왔습니다(12분).
발상 3(15분): 그런데 생각해보니까, LS의 마지막 알파벳 몇 개가 같으면 그 부분은 정렬할 필요가 없습니다(LS는 무조건 완전히 반대 방향으로 정렬되어 있고, 정렬 방법이 가장 뒤의 것을 빼와 가장 앞에 붙이기 때문입니다). 따라서 마지막의 같은 원소 개수를 빼야 답이 됩니다.
구현했고 맞았습니다(17분).

D번을 잡았습니다.
앞에서부터 $i$번째 항까지의 mex를 $m_i$라 합시다.
발상 1(2분): 뭔가 DP스럽게 생겼습니다. 순열의 시작점이 정해져 있을 때, $m_i=min(a_j \mid j\geq i)$입니다. 이는 스택으로 잘 처리할 수 있습니다.
발상 2(4분): $a_0=0$이도록 순열의 인덱스를 잘 돌려 놓아 봅시다. 순열의 시작점이 $i$라 할 때, $m_j = 0$이 $j \geq i$인 모든 $j$에 대해 성립합이다. 따라서, 인덱스를 위처럼 돌려 놓은 상태라면 0번부터 $i$번까지 $\sum mex$의 $i$에 대한 최댓값을 찾으면 됩니다.
발상 3(7분): 그렇다면 이러한 인덱스 구조에서 스택으로 최솟값을 잘 관리하면서 누적 mex를 DP로 구하면 됩니다. 근데 이렇게 하면 시복이 제곱인지 뭔지 잘 모르겠습니다.
발상 4(9분): 스택에는 각 원소가 최대 한 번 들어오고 최대 한 번 나갑니다. 따라서 시복은 선형입니다.
구핸했고 맞았습니다(13분).
순위가 3등이었습니다. 2800대 퍼포가 나오는 것을 볼 수 있었습니다.

E번을 잡았습니다. 참고로 못 풀었습니다.
발상 1(5분): 각 노드를 루트로 하는 트리가 몇 개나 있는지 세면 됩니다.
발상 2(30분?): 완전 이진 트리에서의 답을 미리 구해 두면, 크기 $n$의 이진 트리를 $2^a$짜리 트리와 $n’=n-2^a$짜리 트리로 나누는 것을 반복할 수 있습니다. 두 개의 트리에서 해답에 현재 노드가 나타나는 횟수를 더하면 답이 되므로, 이를 반복하면 됩니다.
발상 3(40분): 그런데 이렇게 하면 각 노드의 수를 계산할 수 없습니다. 이는 전처리 같은 것으로 계산해서 갖다쓸 수 있는 게 아니기 때문에 망했습니다.
포기하고 잤습니다. (시험기간이라 늦게 자지 않으려고 했습니다.)

This post is licensed under CC BY 4.0 by the author.