구사과

POI 2009/2010. Pilots$N$개의 수가 주어질 때, 연속 구간 중 (구간 내 최댓값) - (구간 내 최솟값) $\leq T$를 만족하는 최대 길이의 연속 구간을 찾는 문제이다. $N \leq 3000000$을 만족한다.데큐를 사용해서 Sliding window로 구간 최댓값 / 최솟값을 구하는 알고리즘이 잘 알려져 있다. 이 알고리즘에 inchworm을 적용하여서 문제를 해결할 수 있다. 처음에 [1, 1] 구간에서 시작하여. (최댓값) - (최솟값) $ \leq T$ 를 만족할 때까지 구간의 끝점을 늘린다. 더 이상 늘릴 수 없으면, 시작점을 늘리면서 계속한다. 이러한 식으로 구간의 길이를 최대화하면서 데큐를 관리해 주면 최대 구간의 길이를 알 수 있다. 고려대학교 2017 경시대회. L..

1. 제로스택을 구현하면 되는 단순한 문제입니다. 2. 공항비행기가 올 때 공항 게이트를 골라야 하는 데, 각 상황에서 고를 수 있는 공항 게이트 중 가장 큰 것을 골라야 한다는 그리디 접근을 생각해 볼 수 있습니다. 그 위치를 비워두면서 도착하는 비행기의 수를 늘릴 수 없기 때문입니다. ($i$번째 비행기가 비워둔 자리가 끝까지 비었다면 비우는 의미가 없으니 모순입니다. 그렇지 않다면, 비워둔 자리를 다른 비행기 ($j$번째, $j > i$)가 채울 것인데, 그렇게 하느니 $i$번째 비행기와 위치를 바꾸는 것이 이득입니다. 이런 식으로 계속 진행하면 그리디 알고리즘이 최적임을 증명할 수 있습니다.) 이 알고리즘을 그대로 구현하면 $O(PG)$ 시간이 걸려 시간 초과가 납니다.이를 해결하는 방법은, st..

ARC074 D. Lotus Leaves전형적인 Minimum cut 문제이다. 결국 문제에서 연결하라고 하는 대로 연결 하면 그래프가 나오고, 할 수 있는 것은 그 그래프에서 정점을 제거하는 것이다. 고로, 그래프에서 S / T를 제외한 최소 몇개의 정점을 제거해야 S - T로 가는 경로가 없는지를 구해야 한다. Minimum cut 문제는 몇개의 간선을 제거하냐는 문제인데, 정점 제거 역시 쉽게 간선 제거로 환원할 수 있다. $in(i) -> out(i)$ 로 가는 유랑 1의 간선을 만들어주고, 간선은 끊지 못하게 ($\infty$ 유량) 을 주면 되기 때문이다. 옛날에 글로도 썼다. 시간 복잡도는 $O(N^2M^2)$. ARC075 D. Mirrored내 풀이가 약간 이상했었던.. 시간 제한을 간신..