취미로PS하는사람

앳코더 2000이 되니 rated contest가 ARC밖에 없어서(사실상 AGC는 한두달에 한번이니) 요즘 좀 심심했다. ABC도 각잡고 풀면 좋을텐데 rated가 아니다보니 난이도 2400 내외의 한두문제 보고 풀이 떠올리고 이정도 이상은 귀찮아서 안 하게 되더라. 아무튼 오늘 간만에 앳코더를 쳤고, 퍼포 2330정도로 나름 선방한 것 같다. 앳코더를 볼수록 생각하는 힘은 길러지는데 코딩은 점점 느려지는 것 같다 ㅋㅋ! https://atcoder.jp/contests/arc132/tasks A 두 배열 $R$, $C$가 주어진다. $i$번째 열에는 $R_i$개의 #이, $j$번째 행에는 $C_j$개의 #이 있도록 격자가 채워진다. 각 위치에 대해 #인지 아닌지 판별하는 문제다. $i, j$가 주어졌..

https://www.acmicpc.net/problem/3121 그 테크닉을 배웠다. (2022.1.5 추가: rotating sweep line 이라고 부르는 것 같다.) $N$개의 점이 있을 때, 특정 기울기의 법선 벡터를 가지는 직선에 점들을 정사영하여 그 순서를 알고 싶다. 만약 Naive하게 구현한다면 각도는 최대 $O(N^2)$개, 점들의 정렬에 대략 $O(Nlog{N})$이 소요될 것이므로 시간이 너무 오래 걸린다. 하지만 잘 생각해보면 정렬된 상태는 법선벡터와 어떤 두 점을 잇는 직선의 기울기가 동일해질 때 그 두 점의 위치만 인접한 상태에서 바뀌기 때문에, 점 쌍들을 기울기로 정렬하여 순서대로 두 점의 위치만 바꾸어주면 모든 $N^2$개의 각도에서 정사영한 순서를 알 수 있다. 각도 정..

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