목록/ (146)
블로그 옮겼습니다
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..
https://www.acmicpc.net/problem/2365 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697#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;};int..
https://community.topcoder.com/stat?c=problem_statement&pm=11308 풀이를 떠올린 속도는 나쁘지는 않았는데 cache 의 초기값을 -inf 로 안주고 0으로 줬다가 디버깅하느라 시간이 좀 걸렸다. 트리의 간선의 수 N이 정해지면 모든 노드들의 degree 의 합도 2N 으로정해지기 때문에 노드 수와 degree의 합이 N+1과 2N이 되게 하는 모든 degree의 조합의 최대 점수를 dp로 계산하면 된다. 트리의 노드 수와 트리 노드들의 degree 의 합만 기준에 일치한다면 각 노드의 degree 에 대한 조합이어떻게 되던 그에 해당하는 트리를 만들 수가 있다는 사실을 캐치하는 것이 중요한 것같다.이 것만 캐치하면 dp로는 바로 연결되기때문에. 12345..
LCA(A, C) = C, LCA(B, C) = LCA(A, B) or LCA(B, C) = C, LCA(A, C) = LCA(A, B)가 참이면 존재하는거임
https://www.acmicpc.net/problem/1444 하나의 단어는 알파벳 소문자하나와 대문자 하나로 이루어진다. 소문자가 앞에 나오는 경우와 뒤에 나오는 경우이렇게 두가지 경우가 있다. 알파벳 소문자와 대문자가 번갈아 나오는 문장이 입력으로 들어올 때이 문장은 몇 개의 단어로 이루어 질 것이다. 이 때 여러가지 케이스가 있을 텐데 그중 최소 단어 개수를 찾는 문제이다.예를 들어 aAbAc 가 있으면 aA, bB, Ac 로 이루어 졌을 수도 있고 aA, Ab, Ac 로 이루어 졌을 수도 있는 것이다. 이 문제는 결국 최소 정점 덮개 이다. 최소 정점 덮개란 이분 그래프에서 모든 간선이 자신과 접한 두 정점 중최소한 하나는 선택하도록 할 때 최소로 선택하는 정점의 수이다. 그니까 하나의 정점을..
https://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=2376 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104#include using namespace std;typedef long long ll;const int mod = 1e9+7;const int inf = 0x3c3c3c3c;const l..