알고리즘 공부방

문제 oj.uz/problem/view/IOI20_plants 문제 보기 - 식물 비교 (IOI20_plants) :: oj.uz 문제 보기 - 식물 비교 (IOI20_plants) oj.uz 원 위에 0~N-1의 N개의 수가 배열되어 있는 순열 $A$가 있다. 이 때 $R_i$는 i번째 칸부터 오른쪽으로 연속한 $K-1$개의 수들 중 $A_i$보다 큰 수들의 개수로 정의된다. 수열 $R_i$와 쿼리 (x, y)가 Q개 주어질 때, 가능한 모든 $A_i$에서 $A_xA_y$를 만족하는지, 아니면 두 경우 모두 가능한지 판별해야 한다. 단, 주어지는 $R$는 대응되는 $A$가 적어도 하나 존재하는 수열로 주어진다. $K1; init(node*2, tl, mid); init(node*2+1, mid+1, t..

문제 https://oj.uz/problem/view/IOI19_rect 문제 보기 - Rectangles (IOI19_rect) :: oj.uz 문제 보기 - Rectangles (IOI19_rect) oj.uz N*M 크기의 격자가 들어올 때, 다음 조건을 만족하는 직사각형의 개수를 세야 한다. $2

문제 https://oj.uz/problem/view/IOI19_split 문제 보기 - Split the Attractions (IOI19_split) :: oj.uz 문제 보기 - Split the Attractions (IOI19_split) oj.uz 연결된 무방향 그래프가 하나 주어졌을 때 정점들을 $A$, $B$, $C$ 세 개의 집합으로 분리해야 한다. 조건은 $A$, $B$, $C$의 각 집합의 크기는 이미 정해져 있고, 세 집합들 중 적어도 두개는 하나의 커넥티드 컴포넌트를 이루어야 한다. ($N

문제 https://oj.uz/problem/view/IOI19_shoes 문제 보기 - Arranging Shoes (IOI19_shoes) :: oj.uz 문제 보기 - Arranging Shoes (IOI19_shoes) oj.uz 왼쪽 신발과 오른쪽 신발이 여러 개 있고, 각 신발마다 크기가 같은 신발끼리만 짝을 맞출 수 있다. 처음에는 신발들이 막 아무렇게나 섞여 있을 때, 이 신발들을 짝이 맞는 신발들끼리 붙어 있으며, 같은 짝에서는 왼쪽 신발, 오른쪽 신발 순서대로 배열해야 한다. 사용할 수 있는 연산은 인접한 두 신발을 swap하는 연산일 때, 연산의 최소 횟수를 구한다. ($N

https://oj.uz/problems/source/20 1. garden 첫 번째로, 각 정점마다 상태가 2가지가 있다.1. 최솟값 간선으로 갈 수 있다. ( 이 간선을 전에 안 지남 )2. 최솟값 간선으로 갈 수 없어서 두번째 최솟값 간선으로 간다. ( 최솟값 간선을 이미 지남 ) 따라서 노드들의 상태를 위의 1, 2번 상태 2개로 나누어 만들자.0~N-1 : 1번 노드 / N~2N-2 : 2번 노드 이제 각 노드들에서 다른 노드로 상태가 유일하게 정해지니, outdegree = 1인 그래프라고 생각할 수 있고, 이를 통해 Functional Graph 라는 것을 알 수 있다. 이제 마지막으로 원래 문제로 돌아가서 어떤 정점 P로부터 K번 간선을 지나고 얻을 수 있는 경로를 구해주면 된다. 일단 o..