구사과

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