블로그 옮겼습니다

문제 링크 N

문제 링크 \(1 L; pos.resize(N); for(int i = 0 ; i > pos[i]; auto s = upper_bound(all(pos), 0); auto m = upper_bound(all(pos), L / 2); vector ss = vector(s, m); vector ee = vector(m, pos.end()); reverse(all(ee)); for(int i = 0 ; i

https://community.topcoder.com/stat?c=problem_statement&pm=11817 A, B, X

http://codeforces.com/contest/831/problem/E N > N; for(int i = 1 ; i > a; idxs[a].push_back(i); st.insert(a); update(i, 1); } int pos = 0; ll ans = 0; nums.assign(all(st)); for(int i = 0 ; i

http://codeforces.com/contest/112/problem/D N x >> d; int cnt = 0; for(int j = 1; j * j

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