algoshipda의 블로그

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=2615 m개의 쿼리가 들어 온다. a,b 쿼리는 b가 a의 서브트리에 속하는가? 쿼리가 많으므로 한 쿼리를 O(1)로 처리해야 한다. DFS로 각 노드의 DFS 시작시간과 종료시간을 기록해두면 저 쿼리를 O(1)로 처리 할 수 있다. 각각의 시작시간을 Start, 종료시간을 Finish라 하면 Start(a) < Start(b) and Finish(b) < Finish(a) 이면 b는 a의 서브트리이다. # include <bits/stdc++.h> using namespace std ; int n,m; vector< vector< int > > adj; vector< int > start; vector< int > finish; int main () { int t; scanf("%d",&t); for(int tc=1;tc<=t;++tc){ scanf("%d",&n); int cnt = 0; int curtime = 0; adj. clear (); for(int i=0;i<n;++i){ adj. push_back (vector<int>()); int x; scanf("%d",&x); for(int j=0;j<x;++j){ adj[i]. push_back (++cnt); } } start = vector<int>(cnt+1,0); finish = vector<int>(cnt+1,

A n by n 행렬이 주어진다. a(i,j)에는 i*j가 써져있다. 1<=i,j<=n이다. 이 행렬에 쓰인 숫자 중 x와 같은 것들의 갯수를 구하는 문제이다. 행렬의 각 열과 각 행을 봤을때 같은 숫자는 없다. 따라서 1~n까지 돌리면서 x의 약수이면서 x를 나눴을때 n이하의 숫자가 나오는 것들만 갯수를 세면 된다. O(n) B 1<=n<=10^6 , 1<=m<=10^3 길이 n 의 수열이 주어진다. 이 중 1개 이상의 숫자를 뽑아서 합해서 m의 배수를 만들 수 있는지를 구하는 문제이다. m의 배수라는 것은 결국 합했을때 m으로 나눈 나머지가 0이라는 것을 의미한다. 따라서 주어진 수열에서 중요한것은 그 숫자가 아니라 나눈 나머지이다. DP(i,j)를 현재 i 번째 나머지숫자를 보고 있을때 현재까지 합한 숫자들의 나머지가 j인 경우가 있는가? 라고 정의하면 dp[i][j]가 1일 때 dp[i+1][j+a[i]]를 1이라고 하면 된다. 이 경우O(n*m)으로 풀 수 있다. 문제는 n이 최대 100만이라는 것인데(TLE ㅜㅜ) 비둘기집의 원리에 의해 n>m인 경우는 무조건 가능하다고 처리하면 시간안에 계산 수 있다. i번째를 구할때 i-1만 알면 되므로 슬라이딩 윈도우를 써서 메모리 사용량을 줄일 수 있다. C 1<=n<=10^3인 n이 주어진다. 1<=x<=n인 어떤 x를 맞추기 위해 이 x가 어떤 y로 나눠지냐는 질문을 할 수 있다. 문제는 x를 맞추기 위해서 해야할 질문의 최소 수와 이때의 질문 순서이다. 소수를 구해나가면서 소수의 거듭제곱이 <=n 일 동안 답에 추가하면 된다고 한다. 다른 사람들은 이 방법으로 풀었는데 나는 와닿지 않았다 ㅜㅜ sqrt해서 소수판별을 해도 되고 에라토스테네스의 체로 미리 구해놓고 해도 된다. O(nloglogn) D 모름 E 모름

1. 입력으로 점 A와 B가 주어진다. 점 A,B와 같지 않으면서 유클리드 거리 dist(A,B)>dist(B.C)인 C를 찾는 문제 인데 C가 있을 수 있는 범위가 -100<=x,y<=100이라는 조건이 있어서 그냥 200 * 200으로 돌려 보면 된다. 2. 길이 m인 이진수가 n개 주어진다. 이제 이 이진수들을 재배치 하는데 재배치 순서에 따라 그 이진수들의 cost가 결정 된다. cost는 이진수들을 순서대로 봤을때 그 이진수에서 이전에 등장하지 않은 1의 위치의 갯수의 제곱이다. 즉, 110 -> 100 이라면 110에서 처음 등장한 1의 위치 갯수는 2개 이므로 +4, 100에서 제일 왼쪽 1은 110에서 등장하므로 +0 전체는 4. 이런 식이다. 0<n,m<=20이므로 비트마스트 DP를 사용하면 O(m*2^n)의 시간복잡도로 해결 할 수 있다. 많은 사람들이 그리디로 접근해서 틀렸다. 3. 풀어보고 올리겠다.

https://en.wikipedia.org/wiki/3SUM https://www.acmicpc.net/problem/2473 https://www.acmicpc.net/problem/2470 3sum problem 주어진 리스트에서 i<j<k이고 a[i] + a[j] + a[k] = X를 만족하는 해가 있는지 찾는 문제. 먼저 주어진 리스트를 정렬한다. O(nlgn) i를 고정시키고 오른쪽 범위에서 a[j] + a[k] = X - a[i]를 만족하는 해가 있는지를 찾는 문제를 생각해보자. 이 문제는 O(n)에 해결 할 수 있다. a[j] + a[k] > X - a[i]라면 k를 1 감소 시키고 그 외는 j를 1 증가시킨다. 이러면 O(n)에 만족하는 j, k 를 찾을 수 있다. i를 1씩 증가시키면서 모든 구간에 대해 반복하면 최종적으로 O(n^2)에 답을 찾을 수 있다.

http://codeforces.com/contest/574 A 제일 처음 숫자보다 크거나 같은 숫자가 없을때까지 나머지 숫자중에 제일 큰수에서 1을 감소시키고 제일 처음숫자에 더해주고 답을 갱신하면 된다. 숫자 하나 업데이트하고 나서 다시 처음부터 보지 않고 그냥 뒤에 쭉 봤더니 WA, 그래서 우선순위큐를 써서 없을때 까지 돌렸다. A는 틀리지 말자 ㅜㅜ B DFS로 cycle 길이 재는 문제를 접했던 적이 있어서 DFS로 길이 3인 cycle을 찾으려고 시도하였으나 계속 WA가 떴다. 너무나 당연히 된다고 생각했었는데 마침내 예외 케이스를 찾아냈고 안된다는걸 알았다(DFS에 대해 좀 더 깊이 파봐야겠다.). 그리고 그냥 단순하게 4000*4000 인접행렬 만들어 풀었다.. 메모리 제한 넉넉할땐 걱정하지 말고 잡자. C 2랑 3밖에 못곱하므로 결국 어떤 두 수가 같으려면 소인수분해 했을때 2와 3를 제외한 나머지 부분이 같아야 된다. 그래서 2로 안나눠질때까지 나누고 3으로 안나눠질때까지 나눈뒤에 비교 하면 된다. 쉬움. D 어떤 줄이 사라지는 시간은 왼쪽이 사라지는 시간 + 1, 오른쪽이 사라지는시간 + 1, 자기 높이 중 최소라는 사실은 알아냈으나 이후에 어떤식으로 접근해야 할지 방법이 떠오르지 않았다. DP로 풀면 된다고 하는데 아직 자세히 보지 않아서 모르겠다. ..editorial의 풀이는 와닿지가 않았는데 밑에 보니 dijkstra 풀이가 가능하다고 하더라. 각 블록들을 노드로 생각하고 가상의 소스노드에서 블록의 높이를 가중치로 가지는 간선을 연결한다. 인접한 블록들에 대해서는 가중치 1의 간선을 만들어 준다. 최종 답은 소스에서 다익스트라를 돌렸을때 최단거리가 가장 긴 노드까지 가는 거리가 된다. E 모르겠다.