목록Algorithm (121)
블로그 옮겼습니다
http://codeforces.com/contest/732/problem/E N
http://codeforces.com/contest/277/problem/E 2 src = src; this->sink = sink; } bool spfa(){ vector inQ = vector(size, false); queue q; q.push(src); inQ[src] = true; dist[src] = 0; while(!q.empty()){ int here = q.front(); q.pop(); inQ[here] = false; for(int i = 0 ; i 0 && dist[here] + e.cost b.y;}vector points;int N;int NODE(int x){return 2 + x;}int IN(int x){return 2 * x;}int OUT(int x){return 2 ..
https://www.hackerrank.com/contests/w6/challenges/best-spot/problem 우선 FFT 코드는 명우님의 블로그의 코드를 참고했음을 알립니다. http://blog.myungwoo.kr/54 이 문제는 FFT를 모르면 절대 풀 수 없어 보이고, 안다면 단순한 구현문제로 전락해 버린다.우선 naive 하게 생각해 보았을 때 모든 위치에서 답을 계산해 보면 O((RC)^2) 의 시간이 걸린다.R, C가 최대 500 이기 때문에 시간안에 절대 돌 수 없다.FFT를 사용하면 O(RClgRC) 의 시간이 걸리게 되어 시간안에 돌게 된다. 우선 squared difference (x-y)^2 의 식을 풀어보면 x^2 - 2xy + y^2 이라는 것을 알 수가 있다.어차피..
http://codeforces.com/contest/742/problem/E N쌍의 커플이 있고 이들이 원형 탁자에 앉아 있다. 이 2N 명의 사람들에게 1번음식 또는 2번음식을 주어야 한다. 단 조건이 있다. 1. 커플은 서로 다른 음식을 먹어야한다. 2. 탁자에서 연속된 세 사람이 같은 음식을 먹으면 안된다. 주어진 조건을 만족하는 조합이 있으면 그것을 출력하고 없으면 -1을 출력하는 문제이다. 우선 0번 ~ 2N-1번 사람들에 대해 2i번 사람과 2i+1번 사람을 간선으로 이어보자. 그리고 커플끼리 간선으로 이어보자. 이분 그래프에서 특정 노드에 대해 인접한 노드들은 모두 색이 다르므로 만약 이렇게 했을 때의 그래프가 이분 그래프라면 주어진 두 조건을 만족할 것이다. 그런데 이렇게 하면 무조건 이..
http://codeforces.com/gym/100199/attachments LR Flow 예제.각각의 간선의 하한 L과 상한 R 이 있을 때 모든 간선의 용량을 R - L 로 주고가상의 소스를 만들어 각 노드로 들어오는 하한, 즉 demand flow 의 합만큼의 용량의 간선을 이어주고가상의 싱크를 만들어 각 노드에서 나가는 하한의 합만큼의 용량의 간선을 빼준다.그 다음 maxflow 를 돌려서 최대 유량이 모든 demand flow의 합과 같다면 feasible 한거고더 적다면 feasible 하지 않은것이다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657..
https://community.topcoder.com/stat?c=problem_statement&pm=11781 n
http://boj.kr/14657 문제에서 주어진 세개의 조건을 통해 N개의 문제들은 트리를 이루고 있다는 것을 알 수가 있다. 그럼 가장 많은 문제를 풀기 위해서는 트리에서의 가장 긴 단순 경로를 찾으면 되며, 트리에서의 가장 긴 단순 경로는 바로 트리의 지름이 되기 때문에 트리의 모든 지름 중에 경로상에 포함된 에지들의 가중치합이 최소가 되는 지름을 찾는 문제로 볼 수가 있게된다. 트리의 모든 지름을 체크하기 위해 우선 트리의 중심을 찾고 그 중심을 기준으로 답을 구해보자. 하지만 트리의 중심은 1개 혹은 2개이기 때문에 두개의 케이스를 나누어보자. 1. 트리의 중심이 1개인 경우 트리의 중심이 1개인 경우에는 단순하다 트리의 중심으로 부터 거리가 지름/2 인 노드들까지의 경로들 중 그 경로상에 존..
https://uva.onlinejudge.org/external/127/12775.pdf \(0 = 200\)일 때,Ax + By + Cz = P 위의 디오판토스 방정식의 음이 아닌 정수 해 (x, y, z) 의 개수를 구하는 문제이다.우선 위에서 주어진 두 조건 중 두번째 조건을 주목하자. C / gcd(A, B, C) 가 200이상이라는 말은 일단적어도 입력으로 들어오는 C가 200이상이라는 것을 알 수 있다. 그러면 z를 고정시키고 그에 대한 (x, y) 를 구하는식으로 계산한다치면, 최악의 경우에도 고정하는 z의 개수는 10^8 / 200 이하, 즉 50만개 이하가 된다. 그럼 z를 고정시키고 x, y 를 구해보자. 만약 ..
1for(int subset = bit; subset ; subset = ((subset-1) & bit)){}cs
https://www.acmicpc.net/problem/9169 123456789101112131415161718192021222324252627282930313233343536373839404142#include using namespace std;typedef long long ll;const int mod = 1e9+7;const int INF = 0x3c3c3c3c;const long long INFL = 0x3c3c3c3c3c3c3c3c;struct edge{int to, cap, rev;};vector G[303];void connect(int from, int to, int cap){ G[from].push_back({to, cap, (int)G[to].size()}); G[to].push..