본문 바로가기

알고리즘/코드포스44

cf #656 div3 E - Directing Edges(위상정렬, 사이클 유무) https://codeforces.com/contest/1385/problem/E 방향그래프와 무향그래프가 섞인 그래프에서 위상정렬을 구해야 해서 헷갈렸다. 위상정렬 결과로 사이클 판단하는 방법도 숙지해 뒀어야 하는 문제 정점u,v사이엔 최대 하나의 무향또는 유향간선만 존재하는 그래프가 주어진다. 유향간선을 적절히 조정해서 accyclic그래프를 만들 수 있다면 그 간선들을 출력하라 손으로 좀 그리다보면 유향간선만 가지고 사이클이 존재하지 않는다면 항상 정답이 존재함을 알 수 있다. 유향간선 기준 ind로 topological sort를 한 순서벡터로 각 정점마다 순서를 매긴다. 유향간선 u->v 중 rank[u]>rank[v]인 경우가 존재하면 사이클이 있다는 것 의미함. 사이클이 없다면 ,모든 간선을.. 2020. 7. 20.
cf #653 div3 F - Cyclic Shifts Sorting (그리디, constructive, sorting, inversion) https://codeforces.com/contest/1374/problem/F 소팅 문제에서 inversion개수로 규칙찾기 원소의 수가 n개인 배열 a에서 다음 연산을 최대 $n^2$번 수행하여 정렬하여라. 정렬 못하면 -1 출력 1. i번째 원소를 맨 앞으로 가져올 수 있다. 2. a의 원소가 모두 distinct하면 위 operation으로 inversion 개수의 parity를 바꿀 수 없다. 따라서 이 때 inversion 개수의 parity가 홀수면 정렬 불가능하다. 3. a의 원소에 중복 원소가 있다면 일단 distinct한 배열로 바꿔준 후에, inversion 개수의 parity가 홀수라면 중복 원소 한 쌍을 swap하여 parity를 짝수로 맞춰주면 된다. 예를들어 $a = [2,1.. 2020. 7. 13.
2019-2020 ICPC, Asia Jakarta Regional - H. Twin Buildings(수학, 기하) https://codeforces.com/problemset/problem/1252/H 바로 전에 포스팅한 문제의 풀이와 유사 L*W로 표현되는 영역들이 주어진다. (L,W n; for (int i = 0; i > l >> w; if (l > w) swap(l, w); a[i] = { l,w }; temp = max(temp, l * w); temp = max(temp, l * w); } sort(a, a + n); for (int i = n - 1; i >= 0; i--) sf[i] = max(sf[i + 1], a[i].second); for (int i = 0; i < n; i++) { ll l, w; tie(l, w) = a[i]; ans = max(.. 2020. 4. 20.
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.

티스토리툴바