구사과

Water Tree (CF 343D)http://codeforces.com/problemset/problem/343/D거꾸로 생각한다. 기본적으로 모든 노드에 물이 채워져 있고, 1 ~ N개의 노드에 물을 비우는 연산을 넣어 줬다고 가정하자. 비우는 연산이라 함은 해당 노드와 그 부모에 있는 물을 모두 제거함을 뜻한다. * Query 1 : v의 서브트리에, 물이 비우는 연산이 적용되어 있는 노드가 있다면, 모두 지워주고, v의 부모에 물을 비우는 연산을 적용한다. * Query 2 : v에 물을 비우는 연산을 적용한다. * Query 3 : v의 서브트리에 물이 비우는 연산이 적용되어 있었다면 0, 아니면 1을 출력한다. 문제가 아주 깔끔해졌으며, dfs number 순서대로 수를 보관해두면, 세그먼트..

http://59.23.113.171/pool/koi_tree/koi_tree.php?pname=koi_tree Observation 1.문제를 쉽게 해서 유사도가 2일 때를 가정해보자. 그 때는 - 부모가 같으면 연결되어 있다. - 부모가 다르면 연결이 안되어 있다.고로 완전 그래프인 컴포넌트들이 떠다니는 그래프를 상상할 수 있다. 부모가 같은 게 뭔가 중요해 보인다는 사실을 알 수 있고, 난 여기서 착안해서 계통 트리를 다음과 같이 재정의했다. * 계통 트리는 S+1개의 노드로 이루어진 트리로, 각각의 노드는 1 ~ N의 개체들을 0개 이상 포함하고 있다. 이 때, 모든 개체는 정확히 한개의 노드에 속한다. 말로 하기가 너무 뭐한데.. 저 말대로 예제를 그려보면 대충 이런 느낌의 트리가 나온다. 이렇..

프리스비 (USACO Gold 2014.12)https://www.acmicpc.net/problem/10649N이 작은 문제다. 1) 비트 DP를 한다. dp(S) = 현재 집합의 추가 가능한 스택 양 이라 정의하면, Min(dp(S\j), Pj - Sum(S\j)) 중 최대인 j를 고르면 된다. 이후 모든 부분집합 S 중에 높이 합이 H 이상인 애들에 대해서 최댓값을 고른다. 2) 그리디를 한다. 집합이 고정되어 있을때, P + W 순으로 정렬한 후 구한 Min(P + W - S) 값이 항상 가능한 순열 중 최대를 낼 수 있다는 것을 증명할 수 있다. 고로 초기에 P+W 순으로 정렬후 모든 집합에 대해서 시뮬레이션하면 된다. 이런걸 그리디로 할 때는, deadline first라는 걸 기억해두면 편한..

http://codeforces.com/contest/618/ 졸리기도 하고 코포를 보고 싶지 않아서 제낄라고 했는데, 이름을 밝힐 수 없는 어떤 분이 자꾸 "코포봐야죠 코포안봐여?" 해서 봤다. ..아 근데 진짜 졸리긴 졸렸음. 한시간 자고 한시 반에 일어났는데 너무 일어나기 싫더라.. A 함정이 있을까봐 걱정했지만 그런거 없었다.4분 (AC) B a|b를 a||b로 써놓고 한참을 찾았다. 하... 19분 (AC) C 문제 자체는 간단하고 쉬운 기하 문제다. 각도정렬을 알면 풀이 나오는 수준. 내가 C를 락하고 열심히 hack을 시도했었는데, 다들 너무 잘짜서 아무 것도 시도하지 못했다. 하지만 정작 systest를 하니까 정말 수많은 사람들이 나가떨어졌고, 나가떨어진 사람들의 소스코드를 열심히 읽고 ..

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

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] 안에 있는 점들이 만약에 볼록 껍질 상 경로를 방해했다면. 볼록 ..