알고리즘 공부방

문제 oj.uz/problem/view/JOI18_bitaro 문제 보기 - Bitaro’s Party (JOI18_bitaro) :: oj.uz 문제 보기 - Bitaro’s Party (JOI18_bitaro) oj.uz 정점 개수 N, 간선 개수 M개의 DAG가 주어진다. 이 때, 다음과 같은 쿼리에 답해야 한다. 정점 v로 오는 경로들 중, 시작점이 u1, u2, ..., uk 중 하나인 경로들을 제외했을 때 최장경로의 길이룰 구하라. $N

문제 oj.uz/problem/view/JOI20_building4 문제 보기 - 건물 4 (JOI20_building4) :: oj.uz 문제 보기 - 건물 4 (JOI20_building4) oj.uz 길이 2N의 배열 A와 B가 주어진다. 각 i에 대해, A, B중 정확히 하나씩 골라 만든 길이 2N짜리 수열이 증가 수열이어야 한다. 또한, A를 정확히 N개, B를 정확히 N개 골라야 한다. 이와 같이 고르는 것이 가능한지, 가능하다면 그 예를 하나 보여야 한다. $N

문제 oj.uz/problem/view/JOI17_sparklers 문제 보기 - Sparklers (JOI17_sparklers) :: oj.uz 문제 보기 - Sparklers (JOI17_sparklers) oj.uz 수직선 위에 N명의 사람들이 폭죽을 하나씩 들고 서 있다. 처음에는 K번째 사람의 폭죽에만 불이 붙어 있으며, 폭죽에 불이 처음 붙은 후로부터 T초 동안만 불꽃이 유지된다. 불꽃이 꺼지기 전에 어떤 다른 사람과 같은 위치에 있게 되면 그 사람에게 불꽃을 옮길 수 있다. 또한, 각 사람이 1초동안 움직일 수 있는 최대 거리인 속도 X가 정해져 있을 때, 모든 사람의 폭죽에 불이 한번씩 붙을 수 있기 위한 최소의 정수 속도 X를 구해야 한다. $N $[1, N]$은 $[K, K]$ -> ..

D문제 oj.uz/problem/view/JOI18_tents 문제 보기 - Tents (JOI18_tents) :: oj.uz 문제 보기 - Tents (JOI18_tents) oj.uz N*M의 격자에 텐트를 배치하는데, 각 텐트별 동, 서, 남, 북의 4가지 방향이 있다. 어떤 두 텐트가 같은 행이나 열에 있다면 이 두 텐트는 서로 마주보고 있는 방향이어야 한다. 이 조건들을 모두 만족시킬 때 전체 텐트의 배치로 가능한 경우의 수를 구하자. $N, M

문제 oj.uz/problem/view/JOI18_construction 문제 보기 - Construction of Highway (JOI18_construction) :: oj.uz 문제 보기 - Construction of Highway (JOI18_construction) oj.uz 트리가 주어지고, 처음에는 1번 노드밖에 없다. 한번의 업데이트 때마다, 지금 존재하는 트리에 하나의 간선을 추가하여 새로운 노드를 붙이는데, 이 때 루트에서부터 새로 붙인 노드까지의 경로의 정점들의 가중치를 일렬로 나열했을 때 만들어지는 수열의 inversion을 출력해야 한다. 또한, 업데이트 이후, 루트에서부터 새로 붙인 노드까지의 경로의 모든 정점들의 가중치는 모두 새로 붙인 정점의 가중치로 바뀌게 된다. $N

문제 oj.uz/problem/view/JOI19_cake3 문제 보기 - Cake 3 (JOI19_cake3) :: oj.uz 문제 보기 - Cake 3 (JOI19_cake3) oj.uz N개의 케이크 조각이 있고, 이중 M개를 뽑아 적당히 배열하여 $\sum_{i=1}^{M}V_i-\sum_{i=1}^{M}|C_i-C_{i+1}|$값을 최대화해야 한다. $M1; node->lc=new Node(); node->rc=new Node(); makeTree(node->lc, tl, mid); makeTree(node->rc, mid+1, tr); } Node *addTree(Node *node, int tl, int tr, int pos) { if(poscnt+1; ret->sum=node->sum+co..

문제 oj.uz/problem/view/JOI19_mergers 문제 보기 - Mergers (JOI19_mergers) :: oj.uz 문제 보기 - Mergers (JOI19_mergers) oj.uz 트리 상의 각 노드는 특정한 색으로 칠해져 있을 때, 트리가 "분할 가능하다"는 것은 트리를 연결된 두 개의 컴포넌트로 쪼개서, 모든 색이 정확히 하나의 컴포넌트에만 속하게 할 수 있다는 것이다. 서로 다른 두 색을 합칠 수 있을 때, 합치는 연산의 횟수를 최소로 해서 트리가 분할 가능하지 않도록 해야 한다. $Ndep[v]) swap(u, v); for(int i=20; i>=0; i--) if(dep[par[v][i]]>=dep[u]) v=par[v][i]; if(u==v) return u; for..

문제 oj.uz/problem/view/JOI19_lamps 문제 보기 - Lamps (JOI19_lamps) :: oj.uz 문제 보기 - Lamps (JOI19_lamps) oj.uz N개의 램프가 꺼져 있거나 켜져 있을 때, 1. 구간을 정해 구간의 램프들을 모두 끈다. 2. 구간을 정해 구간의 램프들을 모두 켠다. 3. 구간을 정해 구간의 램프들을 모두 토글(뒤집는다)한다. 의 3가지 연산을 적용하여 A 상태의 램프들을 B 상태로 만들어야 할 때 연산의 최소 횟수를 구해야 한다. $N