전체 글110 SRM 675 Div.1 LimitedMemorySeries1 문제 링크 : http://community.topcoder.com/stat?c=problem_statement&pm=14088 문제 내용 : 5,000,000만 개의 수 X(i)가 있을 때에, Q 개의 쿼리 query(i)에 대해서 전체 X를 오름차순 정렬하였을 때에 query(i)번째 원소를 출력하는 문제이다. 하지만 메모리 제한이 2MB라서 X를 전부 저장해 둘 수 없다. X에 대한 일차 함수식은 (X(i-1)*A + B) % 10억7 이다. 쿼리 개수는 100개 이하이다. 풀이 1 : 버킷, 평방분할 수의 범위가 0~10억6인데, 이 범위를 크기가 D인 루트개의 구간으로 평방분할한다. X(i) / D의 구간에 X가 몇 개인지 누적해둔다. 그럼 각 쿼리에 대해서 O(D)에 query(i)번째 원소가.. 2016. 6. 21. JOI Open Contest 2016 - Selling RNA Strands 아호 코라식.Output Link를 굳이 따라가지 않고 카운팅해주고, BFS 역순으로 누적해나가면 O(문자열 길이의 합)에 풀 수 있다. 저 코드는 O(문자열 길이의 합 + 답의 합) 2016. 6. 20. Codeforces Round #352 (Div. 1) - D. Roads in Yusland 기본적인 전략은 가장 말단에서부터 최소 가중치의 path cover를 선택하는데, 선택한 path cover가 끝이 나는 지점을 기준으로 그 밑에서부터 현재 지점을 넘어서거나 혹은 현재 지점에서부터 시작되는 path cover 중 또 가장 작은 걸 선택하는 것임. D(x) : depth가 x의 depth 이하인(x or x의 부모들을 향하는) path cover에 대해 x가 포함된 cover의 weight의 음수값(-weight). 이 커버는 x보다 같거나 더 깊은 곳에서 시작해서 최소한 x의 부모까지는 향함. [S. E]를 이미 선택했는데, S+1 혹은 그 위에서 [S, E]를 다시 또 고려하지 않기 위한 값 정도라고 생각하면 되겠다. 마치 구간에 상수 t를 더할 때, 시작점에서 t더하고, 끝점+1에서.. 2016. 6. 19. 2016.6.18 1. memset 쓰지 말자.2. 토글링 할 수 있으면 하자.3. Codeforces Round #352 (Div. 1) D. Roads in Yusland : http://codeforces.com/contest/671/submission/18570054 2016. 6. 18. Codeforces Educational Codeforces Round 13 - F. Lena and Queries 문제 링크 : http://codeforces.com/contest/678/problem/F 세 가지 쿼리가 주어진다. 1. 기울기가 a이고 절편이 b인 선분 삽입2. 이전에 삽입되었던 i번째 선분 삭제3. 현재 선분 집합에서 특정 x 좌표에 대한 최댓값 출력 풀이 1. - Time Limit Exceeded 쿼리를 루트개씩 묶음으로 나눔. 반평면 땅따먹기 문제에서의 부저장소-저장소 방법으로 각 묶음마다 해결함. 3번 쿼리에 대해서는 이전의 묶음들 + 현재 채우고 있는 묶음에서 답을 찾음.부저장소-저장소 컨벡스헐 트릭 방법은 이 링크에 설명되어 있다. http://codeforces.com/contest/678/submission/18520250 풀이 2. - Accepted 오프라인으로 문제를 해결함... 2016. 6. 17. 이전 1 ··· 11 12 13 14 15 16 17 ··· 22 다음