취미로PS하는사람

https://oj.uz/problems/source/378 컨디션 난조인지, 못하는건지 직접 푼 게 하나도 없다... 그나마 1번은 거의 다 접근했으나 계속 꽉 막힌 생각 때문에 최종 답에는 도달하지 못했다. 1. Designated city 문제를 다시 설명하자면, 정점 몇 개를 골라 모든 정점에 대해 그 정점으로 가는 경로 상의 단방향 길을 다 만들 때 나머지 남은 비용을 최소화해야된다. 만약 한 개의 정점만 고른다면 그 정점에서 다른 정점들로 뻗어나가는 비용만 계산하면 되고, 여러 개일 때는 조금 복잡해 보인다. 우선 E=1일 때를 풀자.(이건 나도 직접 풀었다.) 트리에서 임의로 한 정점을 루트로 잡고 어떤 정점을 지정했을 때 비용을 생각해보자. 그 정점이 루트 정점이면 루트에서 내려가는 방향의..

https://oj.uz/problems/source/377 1. Two Antennas (두 안테나) 극한의 스위핑 문제... 우선 쿼리에 변화가 없으므로 오프라인으로 쿼리를 처리해야겠다는 생각을 할 수 있다. R이 증가하는 순서대로 쿼리를 정렬하자. 통신을 할 수 있는 조건은 1 P[i]; sumA[i] = sumA[i-1] + A[i]; } for(int i = 1; i > B[i] >> T[i] >> Q[i]; sumB[i] = sumB[i-1] + B[i]; ans += Q[i]; } for(int i = 1; i = 0) po.eb(i, temp, P[i]); } for(int i = 1; i b.y; return a.x < b.x; }); ll rem = 0; for(int i = 0; i ..

https://www.acmicpc.net/problem/8128 나의 접근 방식은 이러하다. 1. 리프 노드 사이로만 길을 놔야 한다. 이는 너무 당연하다. 2. 가장 점이 많이 포함되도록 길을 놓았을 때 그 점들의 집합은 끊어져 있지 않다. 만약 끊어져있다면 한 쪽의 한 경로와 다른 쪽의 한 경로의 한 끝점을 맞바꾸면 떨어진 두 컴포넌트 사이의 모든 정점도 포함되기 때문에 언제나 최적의 상태에서 위 조건을 만족하지 않을 수 없다는 것을 알 수 있다. 위 두 조건으로부터 최적 정점 집합은 리프 노드가 총 2*k개인 서브그래프라는 것을 알 수 있다. 이 때 포함된 정점 개수를 최대화 해야 한다. 3. 최적 점의 집합은 트리의 지름을 포함한다. 몇 번 그려보면 왠지 그럴 것 같다는 느낌을 받을 수 있다. ..

https://www.acmicpc.net/problem/8125 간선을 반대로 생각하고 위상정렬하면서 사이클이 있으면 zawsze이니까 그 사이클 임의의 한 점으로부터 dfs하여 모든 점을 색칠하고, 사이클이 없다면 경우의 수를 dp로 구해주면 된다. 쉬운 문젠데 메모리 제한이랑 코딩 미스 때문에 상당히 애를 먹었다... 코드 더보기 #include #define fi first #define se second #define eb emplace_back #define em emplace #define all(v) v.begin(), v.end() using namespace std; typedef long long ll; typedef pair pii; typedef pair pll; const int..

https://oj.uz/problems/source/376 중간에 논 시간을 제외하고 대략 5~6시간 정도 풀었다. 총 229점. 1. Examination(시험) 우선 학생들을 두 시험의 합이 큰 순서대로 정렬하자. 그리고 쿼리 또한 C가 큰 순서대로 정렬하면 쿼리를 처리할 때 두 시험의 합이 C 이상인 학생만 고려하면 되기 때문에 스위핑으로 이 조건을 해결할 수 있다. 나머지 A와 B 조건은 평면에서 x>=A이고 y>=B인 구간에서 점의 개수를 세는 것이기 때문에 2D BIT 등을 활용하여 점의 개수를 세줄 수 있다. 2D BIT를 처음으로 짜 봐서 이상하게 짠 것 같은데, 괜찮은 구현을 찾지 못하겠다... 코드 더보기 #include #define fi first #define se second ..