[Codeforces] Hello 2019

https://codeforces.com/contest/1097

 

저번 라운드에 조져놓은 레이팅을 좀 회복했습니다. D까지 굉장히 빨리 풀어냈네요. 그런데 F 풀이는 아직까지 모르겠습니다. 다음에 한가할 때 제대로 들여다봐야 할 것 같습니다.

 

A - Gennady and a Card Game (Code)

앞글자가 같은게 있는지, 뒷글자가 같은게 있는지를 살펴보면 됩니다.

 

B - Petr and a Combination Lock (Code)

 

$N$이 15 이하이므로 $O(2^N)$으로 풀면 됩니다.

 

C - Yuhao and a Parenthesis (Code)

 

괄호쌍 문제를 풀 때 흔히 하는 것과 같이, ( 가 나오면 +1, ) 가 나오면 -1을 합시다. 그렇게 했을 때 중간에 나오는 최솟값을 $mn$, 최종적인 값을 $cnt$라고 합시다. 그러면 $cnt$가 양수일 때 최종적인 값이 $cnt$인 문자열은 최종적인 값이 $-cnt$인 문자열과 매칭이 이루어질 수 밖에 없고 $cnt$가 음수여도 매한가지입니다. 그리고 조금만 더 관찰을 해보면

• $cnt$가 양수인 경우 $mn$이 0보다 작으면 이 문자열은 매칭에 쓰일 수 없다.
• $cnt$가 음수인 경우 $mn$이 $cnt$보다 작으면 이 문자열은 매칭에 쓰일 수 없다.
• $cnt$가 0인 경우 $mn$이 0보다 작으면 이 문자열은 매칭에 쓰일 수 없다.

라는 사실을 알 수 있습니다. 이렇게 매칭에 쓰일 수 없는 문자열은 다 버린 후에, 남아있는 문자열의 $cnt$ 값을 보고 답을 구하면 됩니다. 답은 $cnt$가 0인 것의 갯수/2 + min($cnt$가 1인 것의 갯수, $cnt$가 -1인 것의 갯수) + min($cnt$가 2인 것의 갯수, $cnt$가 -2인 것의 갯수) + ... 입니다.

 

D - Makoto and a Blackboard (Code)

 

$N$의 약수들만 칠판에 등장한다는 보장이 있으므로 맨 처음에는 약수들에 대한 DP를 하는 문제인가 했는데 $10^{15}$보다 작은 수 중에 약수가 거의 2000? 20000개를 넘어가는 수가 있어서 이 방법이 불가능함을 빠르게 깨달았습니다. 이후에 문득 생각이 난 것이, 기댓값을 생각해보면 각 소인수는 서로 독립적이라는 사실이었습니다. 그렇기에 각 소인수에 대해 기댓값을 구하고 곱해주면 끝입니다. 분수를 $PQ^{-1}$로 표현하는 경우, 합과 곱을 그냥 있는 그대로 해주면 된다는 사실을 이용하면 확률 계산을 편안하게 할 수 있습니다.

F를 풀어내지 못한게 아쉽지만 A부터 D까지 정말 빠르고 정확하게 풀어내어 만족스럽습니다 유후