구사과

Problem : 사이클이 없는 유향 그래프 G = (V, E)가 주어졌을 때, 모든 정점을 덮는 최소 개수의 Path를 구하라.Solution : Path에 집착하면 안된다. 간선들로 풀어서 생각하자. Path 상의 간선이 X개면 N - X개의 Path로 커버 가능하니 선택된 간선의 개수를 최대화하면 된다. 간선을 최대화 할 때 제약 조건은 : 각 정점의 indegree에 선택된 간선이 오직 하나, outdegree 오직 하나인 형태로 구성되어야 한다는 것이다.이제 각 노드를 두개로 쪼개자. 하나는 indegree, 하나는 outdegree를 상징한다. 실제 그래프 상의 간선을 저 안에 잘 박아두면 이분 그래프가 생기니 이제 최대 매칭을 구한다. O(VE). https://en.wikipedia.org..

(Goo, 1990)lyrics : http://www.azlyrics.com/lyrics/sonicyouth/tunicsongforkaren.html 카렌 카펜터즈의 죽음이 꽤 유명한 이야기기는 하지만, 그의 생전 노래와 비교해 보면 참 충격적인 tribute이다. Goo 앨범 전체를 두고 봐도 참 우울한 노래. 이 글을 같이 읽어보는 것도 재밌을 것. http://dangerousminds.net/comments/kim_gordons_open_letter_to_karen_carpenter

https://www.acmicpc.net/problem/2430쉽게 가자. 만약에 두 트리의 루트 T1, T2가 주어졌다면 어떨까?* 1. T1과 T2에서 BFS를 돌린다.* 2. 그래프에 모든 에지들을 T1쪽에 속하는지, T2쪽에 속하는지 분류하는 방법을 알려주자면, i - j를 잇는 에지에 대해서 (D(T1, i) + D(T1, j)) / 2와 ((D(T2, i) + D(T2, j)) / 2를 생각해보자. (무게 중심) 두 값중 작은 쪽이 존재한다면, 그 쪽에 속하는 에지로 보내버리고, 만약에 두 값이 같다면 이건 거울대칭트리 그래프가 아니다. 이렇게 하면 두개의 트리가 만들어 진다. 트리가 아닌 다른 게 만들어졌다면 (E != V-1) NO 찍자. * 3. 리프 번호가 같고, 트리의 구성 에지가 ..

소수 없는 수열 (BOJ 4241)https://www.acmicpc.net/problem/4241백트래킹 노잼 ㅠㅠ One way roads (BOJ 7724. CPSPC 2010)https://www.acmicpc.net/problem/7724그래프가 트리인 경우를 생각해 보자. 주어지는 쿼리들은 트리에 있는 정해진 간선들의 방향을 고정시킨다. 이것은 O(N)에 시뮬레이션할 수도 있지만, LCA를 구한 후, 변홧값만 칠해주면 O(lgN)에도 가능하다. (USACO Dec15 Maxflow 참고. http://usaco.org/index.php?page=viewproblem2&cpid=576) 모든 변홧값이 칠해지면, 두 방향 모두를 가르켜야 하는 에지가 존재할 경우 불가능. 한 방향만 가르키면 된다면..

http://oj.uz/problems/view/balkan11_timeismoney처음에 이러한 문제를 딱 보고 생각이 난건, 한쪽의 sum을 고정시키고 진행하는 knapsack 류의 방법인데 (다익스트라가 그렇게 되니까) 해보면 알겠지만 Prim / Kruskal에서 그런 짓을 하는 거랑 다익스트라에서 하는 거랑은 느낌이 많이 다르다 (ㅜㅜ). 정점 V, 간선 E, max(t, c) = M = 255라고 하겠다. O(ElgE * (VM)^2) / O(V^4M^2) 중요한 고찰이 필요하다. 나올 수 있는 모든 MST의 경우의 수를 (Sigma(T), Sigma(C)) 좌표 형태로 좌표평면에 찍었을 때, xy를 최소화하는 점을 골라야 한다. 최소인 점을 찾았다 치고, 그 점에서 y = T/x의 도함수 값..

http://oj.uz/problems/view/JOI13_cake이런 문제를 내는 사람이나 푸는 사람이나 신기하다. Preliminaries1. 저 그대로의 폼으로는 딱 봐도 답이 안 나오는 구조다.. 거꾸로 들어가야 한다. 어떤 원소 T를 먼저 고르고 들어갔을 때, 마지막으로 먹는 원소는 무엇인가? 답은 T가 아닌 가장 작은 수임을 쉽게 알 수 있다. 최솟값을 고르고 들어갔을 때는 O(N)에 계산하는 예외처리를 해주자. 나머지 경우에는 항상 최솟값이 마지막으로 남을 것이다. 최솟값이 a[0]에 저장되어 있다면 선형에 대해서 문제를 풀어주면 된다. 이건 std::rotate를 쓰면 되니까 O(N)에 원이 선형으로 풀렸다.2. 그래서 마지막에 먹는 걸 누가 먹는지 알았는데, 나머지는 어떻게 알까? 나머지..

http://codeup.kr/JudgeOnline/problem.php?id=4854데이터 만들기 어려워보이는 문제다 ㅠㅠ 일반성을 잃지 않고 s e로 가는 최단 경로는 [s, e] 구간을 볼록하게 잇는 (오른쪽으로 계속 회전하는 방향의) 체인이 됨을 알 수 있다. 이는 컨벡스 헐과 동치이다. 증명 : 자명하게도, [s,e] 구간에 있는 점들만 고려해서 만든 convex chain보다 더 짧은 경로는 절대 만들 수 없다. 그 경로를 항상 만들 수 있음을 보일 것이다. 1. [s,e] 안에 있는 점들이 만약에 볼록 껍질 상 경로를 방해했다면. 볼록 ..

https://www.acmicpc.net/problem/1156https://www.acmicpc.net/problem/6065 이 문제 데이터 오류가 있다. 대회 당시 워낙 어려웠던 문제라 이의제기가 안됐을 뿐... http://blog.myungwoo.kr/6 O(N^2Ti) 일단 관찰 하나가 필요한데, 그 날이 끝났을 때 굳이 소독을 어떻게 맡길지 결정할 필요는 없다. 장난감이 필요할 때마다, 그전 상황을 끼워맞춰 가는 식으로 최대한 이득을 보는 상황을 결정하는 것이 필요하다. 그 전날에 상황을 끼워맞출 수 있는 가짓수는 크게 세가지가 있는데 * 1. 장난감을 새로 샀다고 생각 * 2. 그 전에 썼던 장난감을 1번 소독소에서 가져왔다고 생각 * 3. 그 전에 썼던 장난감을 2번 소독소에서 가져왔다..

https://github.com/koosaga/iamcoder

http://codeforces.com/contest/487/problem/E 문제 설명은 생략함. HLD + BCC를 섞은 문제로써 헬문제였따.. 풀이를 대충 요약하겠다. BCC 파트가 제일 어려웠는데, 지금 열거하는 방법으로 BCC를 트리로 묶어줄 수 있다. 꽤나 스탠다드한 방법이 아닐까 싶다. 익혀두자. * 1. Cut Vertex + BCC Component가 정점이 된다.* 2. Cut Vertex와 연결된 BCC Component를 이어줌으로써 트리를 만든다. * 3. BCC Component에서 DFS Number가 가장 높은 애를 BCC Parent라고 정의한다. 이건 내가 쓴 BCC 알고리즘에서, 처음 새 컴포넌트를 spawn한 노드와 동치라고 할 수 있다. * 4. 문제 특성상 각각의 ..