구사과

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. 문제 특성상 각각의 ..

글을 읽기 전에 SCC와 절점 절선 개념을 배우고 오길 추천함. 간단히 요약하자면 그래프에서 사이클 비슷한 건 정점 하나로 묶어버리고 트리라 치는 알고리즘이다.이러한 점에서는 SCC랑 엄청 비슷하다. 실제로 SCC의 무향 버전이라고 생각해도 좋음. SCC는 사이클을 정점 하나라고 묶어버리고 DAG로 만드는 방법이면 BCC는 사이클을 간선 하나라고 묶어버리고 트리로 만드는 방법이다. 결국은 다 사이클이 싫어서 하는 짓임. 사용 용도도 SCC랑 상당히 비슷하다. BCC에는 두가지 종류가 있다. SCC는 하나만 있는데 얘는 좀 다르다. * Vertex-disjoint biconnected component : 그래프에서 절점을 제거함으로써, 컴포넌트를 나눔 * Edge-disjoint biconnected c..

https://www.acmicpc.net/problem/1859 O(N^2lgN)Ti / Pi 증가 순으로 정렬된 시험 결과들을 토대로 avg(D)를 정의하자. avg(D)는 그리디 전략으로 D개의 과목을 드랍했을 때 베시의 점수이며, (T(N-D+1) + .... T(N)) / (P(N-D+1) + ... P(N)) 이다.이 때 베시가 더 좋은 점수를 낼 조건은 Sum(T) / Sum(P) > avg(D) 를 만족하는 크기 D의 집합이 있다는 조건이다. 비슷한 유형을 풀어보면 알겠지만, 이는 Sum(T - avg(D) * P) > 0 을 만족하는 크기 D의 집합이 있다는 것과 동치이다. Sum(T - avg(D) * P) > 0을 만족하는 집합이 있는지... 는 굳이 말 안해도 다들 알겠지만, 1 ~..

https://www.acmicpc.net/problem/6007 O(N^4)Maximum Toll Cost의 경우의 수가 O(N)이니. 이걸 고정시키고 O(N^3) Floyd Warshall을 돌리면 된다. Toll cost T보다 값이 크면 그 근처에 있는 에지들을 몽땅 날려버리고 플로이드. 반복 반복... 시간 복잡도는 O(N^4). TLE다. O(N^3)플로이드 와셜의 루프. For(i, j, k) dist[j][k] = min(dist[j][k], dist[j][i] + dist[i][k]);를 생각해 보자.맨 바깥쪽 루프에서 도는 것은 중간 경유지이다. 2차원 배열에 중간 경유지를 모두 돌면서 업데이트하는 것이다.그러면, 어떠한 j , k에 대해서, j -> k로 가는 최단 경로가, i까지 경..

http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-introduction-to-algorithms-sma-5503-fall-2005/video-lectures/lecture-18-shortest-paths-ii-bellman-ford-linear-programming-difference-constraints/30분 정도부터 보면 된다. 간략히 말하자면 변수 x1 ... xn N개와, xj - xi

https://en.wikipedia.org/wiki/Karger's_algorithm 그래프에서의 Minimum Cut은 그래프의 컴포넌트를 2개로 쪼개는 데 삭제해야 하는 간선의 개수를 뜻한다. (가중치를 붙여서 일반화한 경우도 있다. 지금 소개하는 알고리즘은 그 경우는 해결하지 못하는 걸로 알고 있음)이 중 정점 S와 T의 Minimum Cut을 구하는 것은 (즉, S와 T를 서로 다른 컴포넌트로 쪼개는 데 필요한 간선수) 알고리즘이 알려져 있다. (http://amugelab.tistory.com/entry/%EC%9C%A0%EB%9F%89-%EA%B4%80%EB%A0%A8-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%A0%95%EB%A6%AC) Minimum Cut의..

http://www.koistudy.net/?mid=prob_page&NO=2058 재밌는 문제.. 텔레포터를 타고 여기저기 옮겨나간다는 문제의 개념이 상당히 당황스러울 가능성이 높다. 막히지 않으려면 "그래프"라는 사실을 빠르게 파악해야 한다. 나뉘어진 선분 구간은 정점이고. 텔레포트는 간선이라는 것을 관찰하면 * 경로 간선의 개수를 최대화 * indegree와 outdegree는 모두 1이다 (시작 끝점 빼고) * 텔레포터의 설치는 두 정점 i, j의 나가는 간선의 교환이다 이 사실을 파악하면 문제가 상당히 깔끔해진다. 먼저 그래프의 성질을 관찰하자. * 컴포넌트 내의 indeg / outdeg가 모두 1이면 컴포넌트는 사이클을 이룬다. * 고로 그래프는 사이클 컴포넌트들의 집합이다.. 근데 시작 끝..