[Codeforces] Round #457 (Div. 2)

http://codeforces.com/contest/916

 

시간대가 조금 안좋았지만 그래도 해봤습니다! 총 5문제였고 A C는 Accepted, B는 Wrong Answer였습니다. 출제자들이 B 문제에서 Greedy 알고리즘을 정해로 생각하고 문제를 출제했으나 반례가 발견되어서 Unrated된 비운의 라운드입니다. 저는 78등을 기록해서 만약 rated 됐다면 rating이 엄청나게 올랐을텐데 아쉽습니다.

  

A - Jamie and Alarm Snooze

 

그냥 모든 경우에 대해 다 따져서 구하면 됩니다. 24시간은 1440분이므로 많아봐야 1440번만 반복하면 답을 알아낼 수 있을 것입니다.

 

https://github.com/blisstoner/Codeforces/blob/master/Round 457/A.cpp

 

B - Jamie and Binary Sequence

 

저(와 출제자를 포함한 대다수의 참가자들)는 Div. 2의 B번 문제임을 감안할 때 쉬운 문제일 것이라고 생각했고, 그래서 대부분 y를 감소시키기 위해 일단 주어진 수를 이진수로 쓴 후, k와 같을 때 까지 큰 지수를 하나 작은 지수 2개로 쪼개는 방식으로 해결했습니다.(예를 들어 23 5의 경우, 23 = 10111(2)이므로 2^4를 2^3 2개로 만들어 3 3 2 1 0을 답으로 출력)

 

그러나 1 7이라는 입력에 대해 Greedy한 알고리즘은 -2 -3 -3 -3 -3 -3 -3 -3 이라는 답을 내는데 사실 -2 -2 -2 -3 -4 -5 -5가 Lexicographical order 상으로 앞서게 됩니다. 이를 해결하기 위해서 Greedy 알고리즘을 살짝 변형해야합니다.

 

일단 y가 작아야하는건 명확하니 Greedy한 방법으로 최대한 분해해나갑니다. 1 7의 경우, 우선 1을 2진수로 표기하면 2^0이니 0이고, 이것을 -1 -1로 분해하고 다시 -2 -2 -2 -2로 분해합니다. 그 다음 분해하면 8개가 생겨 k보다 많아지므로 이제 y = -2임이 확정됐습니다. 달라지는건 지금부터입니다. 이제 -2 -2 -2 -2에서 각 -2를 -3 2개로 쪼개는 것이 아니라 제일 끝의 것만 쪼개나갑니다. -2 -2 -2 -2 => -2 -2 -2 -3 -3 => -2 -2 -2 -3 -4 -4 => -2 -2 -2 -3 -4 -5 -5 

 

이렇게 하면 풀 수 있습니다.

 

C - Jamie and Interesting Graph

 

1에서 N으로 가는 shortest path와  minimum spanning tree 둘 다를 그냥 edge(1,2), edge(2,3), edge(3,4) , ... , edge(N-1,N)으로 만들어버립시다. N보다 큰 적절한 소수 P를 찾고, edge(1,2),edge(2,3),...,edge(N-2,N-1)의 weight은 1로 두되 edge(N-1,N)의 weight은 P-N+2로 두면 shortest path와 MST가 전부 소수가 됐습니다. 그러고나서 다른 edge들은 그냥 굉장히 큰 값(P는 아무리 커봐야 2N을 넘을 수가 없으므로 대충 1000000 정도 줘버리면 됨)을 대입시키면 됩니다. 아이디어만 떠올리면 쉬운 문제였습니다.

 

https://github.com/blisstoner/Codeforces/blob/master/Round%20457/C.cpp 

 

D는 풀이를 보니 Persistent Implicit Segment Tree이 필요하다고 하고(태어나서 처음 들어봤습니다.) E는 전혀 감이 안오네요. ABC는 평소보다 조금 쉽고(비록 B에는 오류가 있었지만) DE는 평소보다 매우 어려웠던 것 같습니다. A를 풀 때 영어가 안 읽혀서 조금 고생했지만 확실히 구현 속도는 향상되고 있는 것 같습니다. (A 5분, C 17분, B 34분) 그리고 hack이 100점이나 주니까 D E를 읽어보고 못 풀겠다 싶으면 빠르게 hack을 하는 것도 좋을 것 같습니다.

 

Unrated인게 너무 아쉽습니다 ㅠ_ㅠ