구사과

소수 없는 수열 (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. 그래서 마지막에 먹는 걸 누가 먹는지 알았는데, 나머지는 어떻게 알까? 나머지..