그래프 이론에서 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에서 규칙이 보였다 (..) 왜 되는지는 모르겠지만 아무튼 규칙대로 짜..
sort(a, a+n, [&](const pnt &a, const pnt &b){if((pi(a.x, a.y) > pi(0, 0)) ^ (pi(b.x, b.y) > pi(0, 0))) return pi(a.x, a.y) > pi(b.x, b.y);if(ccw(a, b) != 0) return ccw(a, b) > 0;return hypot(a) < hypot(b);});앞문제를 풀다가 발견한 코드. 1 2 3 4 사분면에 상관없이 각도정렬을 할 수 있다. + 5.21 업데이트. 각도가 같을 경우 거리순으로 정렬한다. (hypot(p) = p.x^2 + p.y^2, pi = make_pair) + 2017.8.14 업데이트. 코드 길이를 많이 줄였다.
1. Antenna http://amugelab.tistory.com/entry/problem-solving-20160130 에 있는 phone cell 문제 + binary search. https://github.com/koosaga/olympiad/blob/master/CEOI/ceoi06_antenna.cpp 2. Queue N이 작은 케이스에서 시작하자. 이 때는 linked list의 요령으로 문제를 풀 수 있다. prev(i) = i번의 왼쪽 원소, next(i) = i번의 오른쪽 원소라고 했을때, 초기값은 i-1, i+1로 가득 차 있고, 질의가 들어왔다면, 일단 A를 삭제하고, B의 앞에 A를 박으면 된다. 방법은 생략. 이러한 식으로 처리한 후, 후에 배열의 값을 모두 저장해놓고, 그냥..
(LCD Soundsystem, 2005)
https://www.acmicpc.net/problem/12010 이해가 안가면 이 글과 참고해서 보면 좋다 : http://usaco.org/current/data/sol_landscape_platinum_open16.html여담으로 이 문제는 KOI 2005 소방차와 상당히 유사한 문제다. 같이 보면 좋을 듯 하다. http://koistudy.net/?mid=prob_page&NO=313 1. O((NK)^2)dirt의 개수만큼 위치를 저장해 놓은 수열을 펴보자. 예를 들어 3, 1, 5, 1과 같이 수열이 주어지면 0, 0, 0, 1, 2, 2, 2, 2, 2, 3과 같은 형태로 수열을 바꾸는 것이다.수열 A, B가 있을 때 진행하는 연산에 대해서 다시 생각해 보면* 1. 추가 -> 수열 B에 ..
- Total
- Today
- Yesterday