다음과 같은 참고 자료들이 있으니 같이 보자. 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..
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번 쿼리 때문에 굉장히 어려운 문제가 되었다.해법을 이해하기까지도 상당히 힘들었는데, 결론부터 말하자면 다음 네 값을 관리해줘야 한다 : 구간 합, 구간 최댓값, 구간에서 최댓값이 자신의 값인 원소의 수, 구간 두번째 최댓값. 두번째 최댓값은 최댓값보다 작아야만 한다. 먼저 이 값들을 제대로 관리했다면,..
그래프 이론에서 Dynamic Connectivity Problem은, * 1. 정점 u, v를 잇는 간선 추가 * 2. 정점 u, v를 잇는 간선 제거 (이미 있다고 치자.) * 3. 그래프 상에서 두 정점이 연결되어 있는지 체크와 같은 질의가 주어졌을 때, 이러한 질의를 빠르게 응답하는 방법을 찾는 문제이다. O(Q|V|) 나 O(Q|E|) 정도에는, 기본적인 그래프 탐색 알고리즘으로도 아주 쉽게 풀수 있지만, 더 나은 복잡도를 내기는 쉽지 않은 문제이다. 2번 쿼리가 없다면 union-find data structure (링크) 를 사용해서 쉽게 풀 수 있지만, 더 복잡한 질의가 들어왔을 때는 쉬운 풀이가 존재치 않는다. 일반적인 경우 이 문제의 해법은 매우 어려워 보인다 (링크). 하지만, 오프라..
https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=639&page=show_problem&problem=4917 설명이 개판인 점은 양해 부탁한다 (풀이 쓸 시간이 없음.. ㅠㅠ) 어떠한 시간에 대해서 겹치는 구간이 100개인데, 이는 임의의 interval i 에 대해서, sj < si이며 자신과 교차하는 interval이 100개 이하라는 것으로 해석할 수 있고, 고로 모든 교차 쌍의 개수가 100N개 이하라는 결론으로 귀결된다. 요트를 모두 시작점 순으로 정렬하자. 만약에 요트가 단 하나라면, 간단한 dynamic programming을 통해서 O(N)에 해결할 수 있다. 문제는 요트가 두개라는 ..
(5.14 첫 작성) 대회때 100 / 26 / 100점을 받았다.http://apio2016.org/results/ Problem 1. Boat처음 봤을 때 어려워 보이지는 않았고, 어쨌든 대회 시간 안에 풀수 있을 것이라 생각했다. 실제로도 아주 어려운 문제는 아니었지만, 완전히 잘못된 풀이에 낚여서 1시간 이상을 허비한 게 아직도 아깝다. 그걸로 코딩까지 했으니 원.. 틀린 아이디어를 완전히 버리고, subtask를 읽어나가면서 차근 차근 다시 생각하니, 이 때는 쉽게 풀렸다. 먼저 편의상 interval을 [ai, bi+1) 형태로 처리하자. 이러한 형태의 문제에서 가장 큰 걸림돌은 구간의 길이가 크다는 것이니, 어떠한 긴 구간을 빠르게 처리할 수 있는 방법을 고민해봐야 한다. 좌표 압축을 통해서..
결론 : 92등으로 R3 진출 + 티셔츠. 뭐랄까.. 내가 이때 약간 졸린 상황이라서, 그냥 500등 안에 드는 걸 목표로 하고 대회를 봤다. A는.. 처음에 DP같은 걸로 접근하다가 뭔가 이상한거 같아서, 트리를 그려놓고 빅픽쳐 (?) 를 보니까 이해가 갔다. 아주 좋은 문제라고 생각한다. (19:37 Small, 20:00 Large) B는 이상하게 어려웠다. 처음에 내 실수로 머리보다 손이 앞서서 이상한 코드를 짰었는데, 예제 안나오는 걸 보고 이대로 하다가는 말리겠다 싶어서 밀고 딴 문제 생각하다 다시 왔다. 다시 와도 polynomial 풀이가 생각이 안 나서 그냥 brute force를 짰는데, 이상하게 brute force에서 규칙이 보였다 (..) 왜 되는지는 모르겠지만 아무튼 규칙대로 짜..
- Total
- Today
- Yesterday