Codeforces Round 894 (Div. 3)

8월 24일에 진행한 코드포스 894번 대회 일지입니다. 1600+에서 제대로 참여한 사람이 저밖에 없기도 하고, 잘한 건지는 모르겠는데 아무튼 버츄얼 퍼포는 블루입니다. ㅠㅠ

0:00~0:06

• A번을 잡았습니다.
• 무슨 더러운 구현 문제였습니다.
• 3A 치고는 조금 오래 걸렸습니다.

0:06~0:10

• B번을 잡았습니다.
• 전의 숫자보다 더 크거나 같으면 쓰고, 아니면 지워서 얻은 시퀀스가 있습니다. 이 시퀀스를 만들 수 있는 처음 시퀀스를 아무거나 쓰면 됩니다.
• 그러면, 전의 수보다 작은 수만 골라서 두 번씩 써주면 됩니다.

0:10~0:19

• C번을 잡았습니다.
• 히스토그램 모양으로 만들어놓은 배열 다각형이 y=x 대칭이 되는? 뭐 그런 느낌의 문제였습니다.
• 누적합을 이용해서 대칭 배열을 만들면 O(n)에 구현할 수 있습니다.
• 범위 체크를 안해서 런타임이 두 번 터졌습니다.

0:19~0:39

• D번을 잡았습니다.
• 서로 다른 수 n개를 넣으면 nC2입니다.
• 이미 있는 수를 하나씩 더 넣으면, 그만큼 개수가 늘어납니다.
• 즉, $_{r-1}C_2<n< _rC_2$ 를 만족하는 r을 찾은 뒤 몇개 더 넣어주면 됩니다.

0:39~0:58

• E번을 잡았습니다.
• 마지막으로 보는 영화가 무엇인지가 d에 의해 깎이는 엔터테인먼트량을 결정합니다.
• 따라서, 마지막으로 볼 영화 하나를 고르고 그 앞에서 가장 큰 m-1개를 잡으면 됩니다.
• pq를 이용하면 nlogn에 구현할 수 있습니다.

0:58~1:48

• 놀았습니다.
• 근데 F가 보였습니다.
• F번을 잡았습니다.
• 우선 다음과 같은 관찰이 필요합니다: 처음 n일동안 계속 스펠을 세게 한 뒤, 한 번에 모든 몬스터를 격파할 수 있습니다.
• 그렇다면, 몬스터를 두 집합으로 나눠서 각각을 한 가지 스펠으로 처리하면 됩니다.
• n개 중 몇 개의 몬스터를 택해 구할 수 있는 힘의 총합으로 가능한 모든 수를 알고 있다면 됩니다. 나이브는 $2^n$이므로 불가능합니다.
• 그런데, 생각해보면 몬스터의 힘의 총합은 최대 1e6입니다. 즉 냅색 DP를 잘 이용하면 풀 수 있습니다.
• 냅색을 구현할 때 set을 사용하면 시복이 $O(ns log^2(ns))$이 되므로, int[]을 사용해서 $O(n^2s)$으로 줄여야 합니다. 근데 뭐 줄이면 됩니다. 이것 때문에 3번 틀렸습니다.

1:48~2:15

• 놀았습니다.
• junwoojune, equinox_, denniskim에게 E 및 F 풀이를 설명했습니다.
• 잤습니다.

후기

• 아쉬웠습니다. rated로 치환할 때 블루 퍼포였습니다.
• 중간에 놀지 말고 할걸 싶었습니다(만 언레죠?)
• 퍼플은 언제 갈 수 있을까요?