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)$

---

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