[CF 1187C] Vasya And Array - 1800 문제 설명 : n개의 수로 이루어진 수열이 있다. 이 수열에 대해 설명하는 m개의 정보로 수열을 추청해야 하는데 정보는 다음과 같다. t=0일 때는 구간 [l,r]에 해당하는 수가 non decreasing(같거나 오름차순)이고, t=1일 때는 not non decreasing이다. 풀이 :테스트 케이스를 직접 손으로 쓰면서 계산해보면 솔루션은 쉽게 나온다. t=1일 때 나온 구간[l,r]들의 합집합을 구해서 t=0일 때의 구간이 이 합집합에 완전히 포함되지 않기만 하면 된다. 문제는 이를 어떻게 구현하느냐이다. 나도 이 문제를 풀 때 여기서 애를 먹었다.예를 들어 구간[2,3]가 합집합이고 [1,4]가 t=0일 때의 구간이라고 하자. 단순히 ..
[Codeforces 1081D] Maximum Distance -1800 문제 설명 : n개의 vertex와 그 중에서 k개의 special vertex를 가지는 그래프가 주어진다. 문제는 각 special vertex간의 최장거리를 구하면 되는데, 이 문제 내에서 정의하는 '거리'란 edge들의 가중치의 합이 아닌 edge들의 가중치 중에서 가장 큰 값을 거리라고 정의한다. 예를 들어서 1->2로 가는데 가중치가 10, 2->3으로 가는데 가중치가 20이라면 1->3으로 가는 거리는 30이 아닌 20이 되는 것이다. 풀이 : 이 문제는 MST(minimum spanning tree)로 풀면 된다. 즉 edge의 가중치를 오름차순으로 정렬한 뒤, special vertex가 모두 connected될 때..