https://www.acmicpc.net/problem/2543 Interval Graph에서의 Vertex Cover의 개수라는 말로 이 문제를 한줄요약할 수 있다. 하지만 말하는 그대로 dp를 짜기에는 상황이 너무 복잡하다. dp가 애초에 되는지 잘 모르겠다. 여기서 Vertex Cover의 정의를 잠깐 훑고 가자면 "그래프의 모든 간선에 대해, 최소 1개의 정점이 집합 S에 속하도록 하는 정점의 부분집합 S" 이다. 때문에 S의 여집합 I는 "그래프의 모든 간선에 대해, 최대 1개의 정점이 집합 I에 속한다" 라는 성질을 만족한다. 즉 I는 그래프의 독립 집합이다. 즉 Vertex Cover의 여집합은 Independent Set이라는 것을 알고 있으면 이 문제를 풀 수 있다. Interval G..
APIO 2015 작성중인 지금 시간은 토요일 오후 8시. NDA가 있어서 공개는 좀 늦을듯. A : 만들어 놓을 값을 정해놓은 후 (parametric 엇비슷) dp를 돌리면 된다. APIO 역대 문제를 감안하면 제일 쉬웠던 문제인듯. 섭테 케이스 나눠서 짜게 한거 뭐 이해는 간다만 좀 별로였다. (C번도 그런 식이긴 하지만 뭐..) 여담으로 아무 생각없이 짜서 아직 내 풀이가 왜 되는지 모른다. 그냥 어셉먹기에 그런 줄 알았다. B : N^2 다익스트라 + NM 그래프 생성으로 57점 긁었다. 개인적으로 그 57점이 이번 대회 가장 쉬운 섭테였다. N = 30000은 풀이가 정말 다양했다. 내가 본 복잡도가 N^1.5 / N^1.5lgN / Nlg^3M / N^2 (...) 인데 N^2 커팅은 AC고..
당시 대회에서 실제로 맞닥뜨린 문제인데, O(NlgN) 풀이에 꽤 근접했지만 (ㅠㅠ) 결국 제대로 된 풀이를 만드는 데 실패하고 O(N^2lgN) 의 풀이를 짤 수밖에 없었다. 문제는 상당히 단순하다. 이것저것 description이 복잡하게 들어와 있지만 요약하자면 K = 1인 경우 N개의 (Ai,Bi) 쌍이 주어졌을 때 |Ai - X| + |Bi - X| 를 최소화 하는 X를 찾으면,K = 2인 경우 N개의 (Ai,Bi) 쌍이 주어졌을 때 min(|Ai - X| + |Bi - X|,|Ai - Y| + |Bi - Y|) 를 최소화하는 X,Y를 찾으면 된다. K = 1인 경우는 쉬운 그리디 알고리즘이 존재한다. 2N개의 원소가 들어있는 A + B 집합에서의 N번째 원소가 답이다. 복잡도는 O(NlgN) ..
https://www.acmicpc.net/problem/9495 혼자 못풀고 결국 풀이를 봤는데, 풀이가 상당히 멋져서 소개. 득점을 하는 방법을 쭉 따져보자.1. 절대 'x'로 득점을 할 수 없다.2. 'o'로 득점을 하려면 주위에 있는 '.' 들은 모두 차있어야 한다. 즉 주위에 있는 '_'에서 득점할 수 없다.3. '_'로 득점을 하려면 주위에 있는 'o' 들은 모두 차있어야 한다. 즉 주위에 있는 'o' 에서 득점할 수 없다. 벌써 답이 나왔다. 인접한 'o' - '.' 쌍을 모두 이었을 때의 최대 독립 집합 정점 수 를 계산하면 이 문제를 풀 수 있다. degree가 0인 'o'는 없음이 문제 조건에 있으며, '.'는 그냥 넣어줘도 무방하다.새롭게 생기는 그래프는 일단 격자 그래프의 subgr..
https://www.acmicpc.net/problem/1210 1. 최소 코스트 구하기 문제를 뒤집어서 에지를 막을 때 일정한 코스트가 든다고 가정한다면, 이 문제는 Minimum Cut이라는 유명한 문제로 바뀐다는 것을 알 수 있다. Minimum Cut은 Maximum Flow와 동치임이 잘 알려져 있으므로 이러한 문제는 쉽게 풀 수 있다. (http://koistudy.net/?mid=prob_page&NO=1236)다만, 애석하게도 이 문제에서는 정점을 막을 것을 요구하고 있기 때문에 이것만으로는 안 풀린다. 하지만 약간의 변형을 거치면 이 역시 Minimum Cut을 사용해서 쉽게 풀 수 있다. 정점을 In(i), Out(i)라는 두 정점으로 분할하자. In(i)는 이 정점으로 들어오는 간선..
이번 라운드는 할말이 별로 없는듯.. 푼 순서대로 서술한다 A 이 라운드가 dynamic scoring 인줄 몰랐다 맨 처음엔. 내가 너무 싫어하는 lexicographical + bracket 의 연속이라 정말 풀기 싫었는데 5분만에 E번을 푸는 사람이 나오면서 아 이거 dynamic scoring이구나를 깨닫고 던졌다. 결국 라운드 끝날 때 A가 가장 어려운 문제로 확인. 솔직히 딱 봐도 어려워 보인다. E 5분만에 AC가 나와서 아 저거 복붙충 아니냐 **.. 은 농담이고. 쉬운가 싶어서 바로 봤다. (다만 3~5분 AC는 복붙이 맞는 거 같다) 처음 문제를 봤을때는 풀수 없음을 증명하는게 빠르지 않을까 (...) 하고 당황했는데 제약 조건을 본 후 그냥 평이하게 풀리는 문제임을 확인했다. 20분 ..
http://poj.org/problem?id=2104https://www.acmicpc.net/problem/7469 1. Naive - O(MNlgN)더 이상의 자세한 설명은 생략..O(N) Selection Algorithm이 있지만 느리면 느렸지 빠르진 않을 듯.여담으로, 잘 컷팅하면 이걸로 2번보다 빠르게 풀수 있다 ㅡㅡ; 2. Query Sorting - O(NlgN + M*N^0.5*lgN)http://amugelab.tistory.com/entry/%EB%A3%A8%ED%8A%B8-%EC%95%BC%EB%A7%A4때문에 역시 자세한 설명은 생략.간단히 설명하자면, 맨 처음 좌표압축을 한 다음에 링크 1번 트릭 + K번째 원소 BIT를 구현해 주면 된다.시간이 간당간당한 편이다.. 버킷 사이..
pdf로 대신한다.
꼭 이걸 써야 되는지 써도 되는지는 모르겠다 공개적인 곳에서 자랑하는 것도 아니고, 그래도 이런 경험을 해볼 일이 얼마나 될라나 싶어서 여기다 대강 글로 적어 남기고 싶다. 사실 겨울학교 전까지만 해도 내가 잘하는 지도 몰랐고 국대에 대한 욕망도 별로 없었는데 (기대치가 없으니), 와서 보니까 내가 생각보다 잘하더라. 겨울학교 끝날 때 시험을 치고 대강 6등? 언저리에 머물렀더니 확실히 유혹이 생겼다. 딱히 잘본것도 아닌데 그렇다고 딱히 못 본것도 아니고 그 점수대가 다 비슷비슷해서. 꼴지를 해도 공부야 했겠지만 그래도 목표치를 조금 높게 잡아보기로 했다. 그런다고 죽는것도 아니고 ㅎㅎ 겨울학교 갔다오고 배운게 참 많다.. 세그먼트 트리를 짤 수 있게 된 것도 사실상 그 이후였고, 컨벡스헐트릭도 몇달만에..
- Total
- Today
- Yesterday