옛날부터 모아오던 문제집인데 이제서야 정리... 대부분 IOI 합숙교육때 봤던 문제들이다. koistudy 1534. 369 마스터http://koistudy.net/?mid=prob_page&NO=1534 수의 개수가 10^8개이다. 단순한 알고리즘으로는 10^8 * lg(10^8) / lg(10) 정도라 아마 TLE가 날 것이다. 하지만 루프가 단순하면 10^8 정도는 무난하게 돌릴 수 있을 테니, 각각의 숫자를 아주 빠르게 판별할 수 있으면 괜찮다.여기서 약간의 전처리를 통해서 판별을 아주 빠르게 할 수 있는데, 100000 미만의 i에 대해서, 해당 수가 369 수인지를 전처리 해두면, 10^10 크기의 수 X는, X / 10^5가 369 수거나 X % 10^5가 369 수이면 369 수이다. 이..
(Ali Bahjati suggested for English translation, so I added some translation below. Thanks for the suggestion!) Day1 여태까지 봤던 올림피아드 중 가장 힘들었던 거 같습니다. railroad / shortcut 콤보에 정신을 못 차리고 아무것도 하지 못한 채 멘탈붕괴... 대회 전에는 별 생각없이 들어갔다가 정말 말 그대로 박살나서 나왔습니다. 이렇게 박살난 건 저만 그런건 아닌듯.. 배점이 너무 이상한 탓에 성적에 큰 상관은 없었던 것이 다행이지만, 여러모로 아쉬움이 많이 남는 날이었습니다. This was the most painful contest that I’ve ever been. I wasn’t reall..
http://acm.hdu.edu.cn/showproblem.php?pid=5306 세 종류의 쿼리를 지원하는 자료구조를 설계하는 문제이다. O((N + Q)lgN)에 해야 한다. * 1. 구간 [L, R]에 a[i] = min(a[i], V) 대입 * 2. 구간 최댓값 * 3. 구간 합 보통 이러한 문제들은 세그먼트 트리에 익숙하면 쉽게 풀 수 있고, 실제로 2번 쿼리까지는 쉬운 문제지만, 이 문제는 3번 쿼리 때문에 굉장히 어려운 문제가 되었다.해법을 이해하기까지도 상당히 힘들었는데, 결론부터 말하자면 다음 네 값을 관리해줘야 한다 : 구간 합, 구간 최댓값, 구간에서 최댓값이 자신의 값인 원소의 수, 구간 두번째 최댓값. 두번째 최댓값은 최댓값보다 작아야만 한다. 먼저 이 값들을 제대로 관리했다면,..
- Total
- Today
- Yesterday