구사과

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..