본문 바로가기

알고리즘/코드포스44

Educational round #72 div2 D - Coloring Edges (방향그래프 사이클) https://codeforces.com/contest/1217/problem/D (editorial 풀이) 방향그래프가 주어진다. 정점(n)과 간선(m)의 최대는 각각 5000이다. 각 간선에 최소한의 색(k)을 칠해서 같은 색의 간선끼리 cycle이 생기지 않도록 하는 k와 그때 간선의 색을 모두 출력하는 문제다. editorial의 설명 -> 간선 (u,v)가 back edge : if there is a path from v to u by edges from dfs tree 문제 풀땐 if there is a 'edge' from v to u by edges from dfs tree 로 생각하도록 하겠다. dfs tree를 그리고 back edge를 추가한 그래프를 떠올려보자. 다음은 1, 2 /.. 2019. 12. 5.
codeforces #603 div2 D - Secrete Passwords ( 이분매칭, disjoint set ) http://codeforces.com/contest/1263/problem/D editorial은 biparite graph 어쩌고로 풀던데, 나는 유파로 풀었다. 문자열이 최대 2e5개 들어온다. . i번째 문자열과 j번째 문자열이 단 한 개라도 같은 알파벳을 사용했다면 두 문자열은 equivalent다 . k번째와 i번째 문자열이 equivalent하고 k번째와 j번째 문자열이 equivalent하다면 i번째와 j번째는 equivalent다. 위 상황에서 컴포넌트의 수를 구하는 문제이다. 간선만 잘 깔아주면 된다. 하지만 n이 커서 단순히 모든 요소를 비교하는 식으로 간선을 이을 수 없다. bool s[MAX][26] = { 0 }; string 형으로 문자열을 입력받은 후, 위에 저장해 뒀다. (.. 2019. 12. 2.
codeforces #600 div2 D - Harmonious Graph ( disjoint set ) https://codeforces.com/contest/1253/problem/D 처음으로 버츄얼이 아닌 실제 시험에서 4솔을 했다. undirected 그래프가 harmonious -> if and only if, For every triple of integers (l,m,r) such that 1≤l> m; fill(uf, uf + MAX, -1); P e[MAX]; vector can; for (int i = 0, u, v; i > u >> v; if (u > v) swap(u, v); merge(u, v); e[i] = { u,v }; } sort(e, e + m); int st = e[0].first, en = e[0].second; for (int i = 1; .. 2019. 11. 20.
codeforces #600 div2 C - Sweets Eating ( 구간합 전처리, dp ) https://codeforces.com/contest/1253/problem/C 굉장히 깔끔하게 떨어져서 마음에 들었던 문제 day n, 하루에 먹을 수 있는 사탕의 최대 개수 m, sugar concentration a 배열이 주어질때, sugar penalty를 사탕을 먹은 날 * ai라고 한다. 이 때 사탕 k개를 먹을 때 sugar penalty를 k = [1,n] 구간에 대해서 모두 구하는 문제이다. 제일 먼저 a 배열을 오름차순 정렬해준다. sugar concentration이 작은 것을 먼저 먹는 것이 유리하기 때문이다. 그리고 잘 생각해보면 사탕 i개를 먹을 때 sugar penalty f(i) = f(i-m) + psum(i) (i>m) // f(i) = psum(i) (i> n >> .. 2019. 11. 20.

티스토리툴바