구사과

다음과 같은 참고 자료들이 있으니 같이 보자. http://web.stanford.edu/class/cs97si/suffix-array.pdf http://web.stanford.edu/class/cs97si/10-string-algorithms.pdf http://blog.myungwoo.kr/57 http://m.blog.naver.com/dark\_\_nebula/220419358547 Suffix Array는 문자열과 부분문자열을 가지고 놀 수 있는 자료구조이다. 이름만 보면 도대체 어디에 쓰는 것인지 잘 이해도 안 가고 왜 배우는 지도 알 수 없을 것이다. 일단, Suffix Array를 통해서 쉽게 풀 수 있는 문제 몇가지를 나열하자면 : * 길이 |S|의 스트링 하나와, Q개의 길이 Ti의 ..

옛날부터 모아오던 문제집인데 이제서야 정리... 대부분 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..