7/25 연습

1. 이상한 수열 (OJUZ #10)

http://icpc.me/11917

http://oj.uz/problem/view/OJUZ10_bizarre

풀이 :

oj.uz에서 처음 봤을 때 아무 생각 없이 62점을 받고 넘겼던 문제다. 100점 풀이 생각 못한 뚝배기를 매우 쳐라

\(M\)이 비상식적으로 크므로, \(B_i\)의 값을 거의 닫힌 꼴로 구할 수 있을 것이라는 생각을 해야 한다. \(S\)를 오름차순으로 정렬한 뒤, \(B_{n+1}\)의 값 (\(S_1, S_2, \cdots S_n\) 중 서로 다른 수의 개수)이 어떤 \((S_i,S_{i+1}]\)에 있게 되면 이 값은 \(S_{i+1}\)로 수렴하고(편의상 \(S_{n+1} = \infty\)라 두자), 그 전까지는 값이 1씩 증가하게 됨을 어렵지 않게 보일 수 있다.

Time Complexity : \(O(N lgN)\)

---

데이터를 다 썼는데 어제 핫스팟 틀어줄 천사를 찾지 못해서 한 놈밖에 못 풀었스ㅂ니 ㄷ.... 오늘 빡세게 해야지.