Codeforces Round 1064 (Div. 2)

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

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

ㅤ

A 00:03 AC

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

ㅤ

B 00:11 AC

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

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

ㅤ

C 00:17 AC

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

ㅤ

E 00:42 AC

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

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

v >= 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번을 푼 사람이 없어서 이 시점에서 퍼플로 승급한다는걸 확신했다. 모든 상황이 잘 갖춰지고 운까지 따라줘서 이렇게 하이커리어를 찍었다고 생각하지만, 퍼플에 주차해놓지는 않을것이다. 이정도 기량을 내 실력으로 만들어야 더 높게 등반할 수 있을테니..