구사과

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