알고리즘 공부방

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

문제 www.acmicpc.net/problem/19456 19456번: Cocktails In the first line of input there are four space-separated integers $n$, $k$, $B$, $C$ ($1 \leq k \leq n \leq 500$, $1 \leq B, C \leq 10\,000$) --- the number of jars, the reach of the blender, the time needed to use the blender, and the time needed to swap www.acmicpc.net 길이 $N$의 수열이 주어지고, 할수 있는 연산은 1. $A_i$의 비용으로 i번째 칸을 체크 2. $B$의 비용으로 연속된 $k$개..

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

문제 oj.uz/problem/view/JOI19_dishes 문제 보기 - Two Dishes (JOI19_dishes) :: oj.uz 문제 보기 - Two Dishes (JOI19_dishes) oj.uz 두가지 요리가 있고, 각 요리를 완성하기 위해서는 각각 $N$, $M$개의 단계를 거쳐야 한다. 각 단계마다 수행하는 시간이 주어지고, 각 단계를 $A_i$ 시간 이하로 끝낸다면 $B_i$의 보상을 받을 수 있다. 각 요리의 단계들은 순서대로 시행해야 하며, 두 요리의 단계들을 번갈아 가며 하는 것은 허용된다. 이 때 얻을 수 있는 보상을 최대화해야 한다. $N=Y_i)$ 구간에 더해줌 원래 계단 꼴이었고, 뒤쪽 구간에 $P_i$를 더하는 과정에서 깨진 계단을 다시 맞춰주는 형식이니, 요약하자면 ..

문제 https://oj.uz/problem/view/JOI20_ho_t3 문제 보기 - Collecting Stamps 3 (JOI20_ho_t3) :: oj.uz 문제 보기 - Collecting Stamps 3 (JOI20_ho_t3) oj.uz 원 위에 수행해야 하는 작업들의 위치 X, 수행해야 하는 시간 T가 주어질 때 원점에서 출발하여 각 시계방향, 반시계방향으로 움직이며 작업들을 수행해야 한다. 좌표 1칸을 이동할 때 1의 시간이 소요되고, 작업을 T이내에 수행한다면 보상을 받을 수 있을 때 전체 보상의 최대값을 구해야 한다. $N

http://apio-olympiad.org/2016/https://oj.uz/problems/source/184https://koosaga.com/113 3. Gap Subtask 1 한번에 양 끝의 값 2개씩 알아간다고 생각하자. 지금 아는 끝값으로 쿼리를 날리면 그 다음 끝값 2개를 알 수 있다. 사용하는 쿼리의 개수는 ceil(N/2) 개로, 30점을 받 수 있다. Subtask 2 Subtask 2에서는 쿼리의 개수만 중요한 것이 아니라, 한 쿼리가 적은 수들을 덮고 있어야 한다. 만점을 얻기 위해서는 한가지 중요한 관찰이 필요하다.일단 첫번째 쿼리로 최소값과 최대값 s, e를 구했다고 생각하자. [s, e] 구간 안에 gap들은 N-1개가 있으니, max gap < (e-s)/(N-1) 의 상..

Convex Hull Trick은 DP의 시간 복잡도를 획기적으로 줄일 수 있는 방법으로, DP optimization의 세가지 종류 중 하나이다. CHT조아 $dp(i) = min_{j

문제 https://codeforces.com/contest/1187/problem/E 트리에서 어떤 노드를 시작으로 선택한 노드들과 인접한 노드들을 골라 검정색으로 칠하는 과정을 계속 반복한다. 이때 노드 하나를 선택할 때 아직 색칠되지 않은 컴포넌트의 크기만큼의 점수를 얻을 때, 점수의 최댓값을 구하는 문제이다. 풀이 가장 먼저, 처음에 선택하는 노드를 하나 정해놓고 생각해보자. 다음에 선택하는 노드는 그 노드와 연결되어 있는 점이어야 하고, 다음에 선택할 점들을 어떤 순서로 골라도 상관이 없다. 이를 이용하면, 다음을 알 수 있다. 루트 하나를 고정시켜 놓은 트리에서, 각 노드마다 서브트리의 크기를 구하면 그 서브트리 크기의 합이 바로 답이 된다. 이는 트리 DP를 이용하여 구할 수 있다. dp[v..