Codeforces Round 1064 (Div. 2)

퍼플을 달성했다. 블루를 달성한 게 8월이었으니 3달 만이다.

나는 조합을 진짜 싫어하기 때문에 C까지 풀고 D를 보자마자 바로 건너뛰었는데, 그렇게 마주한 E가 체감상 D보다 쉬워서 최고 등수를 찍을 수 있었던 것 같다.

A — 00:03 AC#

주어진 문자열에서 안 바뀌는 문자는 마지막 문자밖에 없기 때문에, 모든 문자는 마지막 문자로 통일되어야 할 것이다. 마지막 문자와 다른 문자의 개수만 세주면 된다.

B — 00:11 AC#

$a = b$일 때 답이 1인 게 자명하다.

$n \le \lfloor a / b \rfloor$라면 모든 위치가 화면 안에 있기 때문에 답이 1이고, 그렇지 않으면 탭을 닫을 때 위치가 바뀌니까 답은 2이다.

C — 00:17 AC#

합치는 연산을 하면, 인접한 두 값 중에 큰 값만 남기 때문에 cost를 최소로 하려면 가장 큰 값을 마지막까지 남겨야 한다. 다시 말하면, 모든 인접한 두 값에 대해 합치는 연산을 해서 cost를 계산하고, 가장 큰 값에 해당하는 비용만 빼주면 된다.

E — 00:42 AC#

D가 조합 문제라서 보자마자 넘기고 E로 왔다. 역시 코드포스답게 그리디 냄새가 나는 비트연산 문제였는데, 나름 비트연산에 강하다고 생각했기 때문에 자신감 있게 바로 풀이를 구상해볼 수 있었다.

각 비트 $k$마다 $2^k$ 뭉탱이를 만들어야 한다고 생각할 수 있고 이걸 충당할 수 있는 건 그때까지 안 쓴 원소들이나, 쓰고 남은 부분들일 것이다. 따라서 어떤 조각 $v$에 대해 $v \ge 2^k$이면 그걸 사용하고, 남은 $v - 2^k$는 나중에 더 낮은 비트에서 재사용하면 된다.

$v < 2^k$이면 $2^k - v$만큼 비용을 들여서 $a$를 올려줘야 한다.

그러니 $v$가 커질수록 들어가는 비용이 줄어들고, 결론적으로 항상 큰 거부터 쓰는 게 최적이라는 걸 이끌어낼 수 있다.

여기까지 생각하고 바로 구현에 들어갔고, 구현 자체는 그리 어렵지는 않았기 때문에 예제 돌아가는 거 보고 바로 제출해서 AC를 받을 수 있었다. 나중에 에디토리얼을 보고 깨달은 건데, 작은 값 두 개를 사용해서 대체하는 건 왜 최적이 안 되는지도 관찰이 필요했었다. 풀 때는 아예 저런 생각 자체를 못해서 오히려 빨리 풀렸나 싶다.

D — 01:26 AC#

유구한 역사와 전통을 지닌 조합 문제는 언제나 풀기 싫은 문제였다. 이런 조합 문제들은 사고 흐름 과정이 비직관적이라고 생각한다.

30분 동안 별생각 다 하다가 결국 $dp[i]$ = '$S$에 속한 원소들의 $a$에서의 개수의 합이 $i$인 경우의 수'로 놓고 풀었다. 풀고 보면 정리된 식은 간단한데 그 식을 얻으려고 온몸비틀기를 해야 하는 게 참.. 이래서 조합 문제가 싫어

나머지 아이디어는 에디토리얼과 같아서 생략한다.

특이하게도 이번 라운드는 A, B, C, D번 문제는 hack이 없고 프리텟이 시스텟하고 똑같았다. 그래서 사실상 이미 4솔은 확정이고, 같은 room에 E번을 푼 사람이 없어서 이 시점에서 퍼플로 승급한다는 걸 확신했다. 모든 상황이 잘 갖춰지고 운까지 따라줘서 이렇게 하이커리어를 찍었다고 생각하지만, 퍼플에 주차해놓지는 않을 것이다. 이 정도 기량을 내 실력으로 만들어야 더 높게 등반할 수 있을 테니..