[Codeforces] Round #507

http://codeforces.com/contest/1039

 

A번 설명이 너무 개떡같아서 풀지못했고 B와 C를 푼 줄 알았으나 C를 날려먹었습니다.

 

B - Subway Pursuit (Code)

 

되게 신기한 문제였습니다. 대충 이분탐색스럽긴 한데, range를 st to en으로 좁혔다고 쳐도 다음 번에는 range가 st - k to en + k로 늘어나기 때문에 4*k 이하로는 범위를 좁힐 수 없습니다. 그러나 k가 10 이하이고 4500번이나 시행을 할 수 있으므로 5*k 정도로 범위를 좁힌 이후에는 범위 안에서 랜덤으로 수 하나를 찍습니다. 이 행위를 계속 하면 굉장히 높은 확률($1 - 10^-10$ 이상)로 답을 맞출 수 있게 됩니다.

 

C - Network Safety (Code)

 

문제의 상황대로 graph를 그려놓고 나면, 2에 각 edge에서 값이 x인 것만 남겼을 때의 component 갯수를 지수로 올리면 그것이 값이 x일 때 A의 종류의 갯수입니다. 2의 거듭제곱을 끝까지 안구해서 system test에서 터졌습니다.

 

최근 4개 대회에서 계속 가장 배점 높은 문제를 system test에서 틀리고 있네요. 반성해야겠습니다.