본문 바로가기

알고리즘225

cf #621 div1&2 D - Cow and Fields (그리디, 정렬, 그래프) https://codeforces.com/problemset/problem/1307/D editorial 참고. 정점 n개, 간선 m개의 양방향 그래프가 주어진다. (n,m m >> k; for (int i = 0, x; i > x; a.push_back(x); } for (int i = 0, u, v; i > u >> v; g[u].push_back(v); g[v].push_back(u); } bfs(1, 0); bfs(n, 1); sort(a.begin(), a.end(), [](int i1, int i2) { return d[0][i1] - d[1][i1] < d[0][i2] - d[1][i2]; }); int ans = 0, mx = d.. 2020. 4. 17.
cf #632 div2 C - Eugene and an array (투포인터) https://codeforces.com/contest/1333/problem/C -1e9~1e9값을 갖는 최대 1e5의 원소 n개의 배열이 주어진다. 배열의 subarray 중 그 subarray의 subarray의 원소합이 0이 아니면 good subarray라고 한다. 주어진 배열의 good subarray 개수를 구하라 [a1, a2, a3, a4]가 good subarray라면 [a1,a2,a3]도 good subarray이다. 하지만 [a3,a4]가 good subarray일수도 있고 아닐수도 있다. ps[1] = ps[4]인 경우 a[2]~a[4]는 bad subarray이다. 문제의 성질을 잘 생각해보면 투포인터로 풀 수 있다. ll n, a[MAX], ps[MAX]; int main() .. 2020. 4. 13.
1차원 직선 위 겹치는 선분들 모든 '교차'하는 선분 쌍에 대한 질의 https://acm-iupc.tistory.com/entry/%EC%84%A0%EB%B6%84%EC%97%90-%EB%8C%80%ED%95%9C-%EC%A7%88%EC%9D%98 *교차하는 모든 선분 쌍의 수 nlogn에 구하는 법은 못 찾겠고 생각이 안난다 (20.4.5) 겹치는 선분에 대한 생각 정리용 포스트 https://www.acmicpc.net/problem/11000 위 문제에서 어떤 시간에 필요한 강의실의 수 = 그 시점에 겹치는 선분의 수 total = 겹치는 선분 쌍의 수 mx = 최대로 겹칠 때 겹치는 선분 수 const int MAX = 2e5 + 4; int n, ps[MAX],mx, total; P line[MAX]; int main() .. 2020. 4. 5.
cf #538 div2 C - Trailing Loves (소인수분해, 수학) https://codeforces.com/contest/1114/problem/C n! 에 어떤 소수가 몇개 들어있는지 로그시간에 파악하는 법 확인. 오버플로우를 피하기 위한 조건문 확인. 최대 1e18의 n과 최대 1e12의 b가 주어진다. n!을 b진법으로 표현했을 때 trailing zero의 수를 세라. (ex. 9800은 10진법으로 trailing zero가 두개 있다.) n!을 b로 몇번 나눌 수 있는지 구하면 된다. b를 소인수분해하여 p ^ x꼴의 인수들에 대해서, n!에 그 하나하나의 인수가 나오는 횟수들의 최소를 구하면 된다. n!에 어떤 소수 x가 몇 개 들어있는지 반환하는 함수 f를 이용해서 풀 수 있다. ll f(ll x) { ll ret = 0; ll t = x; x = 1; .. 2020. 4. 2.

티스토리툴바