알고리즘 공부방

문제 oj.uz/problem/view/APIO19_strange_device 문제 보기 - 이상한 기계 (APIO19_strange_device) :: oj.uz 문제 보기 - 이상한 기계 (APIO19_strange_device) oj.uz parameter t에 대해, 순서쌍 (x, y)는 다음과 같이 정의된다. $x=(t+[\frac{t}{B}]) mod A$ $y=t mod B$ 이 때, t의 disjoint한 구간 n개가 주어지고, 모든 구간의 합집합의 t에 대해, 서로 다른 (x, y)의 개수를 세야 한다. $A, Bfirst; } printf("%lld\n", ans); }

문제 oj.uz/problem/view/APIO20_swap 문제 보기 - 자매 도시 (APIO20_swap) :: oj.uz 설명 인도네시아에는 $N$ 개의 도시가 있고, $0$부터 $N - 1$까지 번호가 매겨져 있다. 또 $M$ 개의 양방향 도로가 있는데, $0$ 부터 $M - 1$까지 번호가 매겨져 있다. 각 도로는 두 개의 서로 다른 도시 oj.uz 정점 개수 N, 간선 개수 M개의 연결 무방향 그래프가 주어질 때, 쿼리로 두 정점 X, Y가 주어진다. 이 때, 한 명은 X에서 Y로, 한 명은 Y에서 X로 이동한다. 이때 두 명이 만나서는 안되고, 한 간선을 가다가 중간에 돌아가는 등의 일은 할 수 없다. 이 때 두 사람이 이용하는 간선들의 가중치의 최댓값을 최소화한 값을 출력하자. $N=0; ..

문제 oj.uz/problem/view/APIO20_paint 문제 보기 - 벽 칠하기 (APIO20_paint) :: oj.uz 설명 성렬이는 자기가 사는 집의 벽을 칠한지 한참 되었기 때문에 다시 칠하려고 한다. 벽은 $N$개의 구간으로 되어 있는데, $0$부터 $N - 1$까지 번호가 매겨져 있다. 이 문제에서, $K$ 가지 다른 oj.uz 길이 N의 배열을 각 칸을 $C_i$의 색으로 칠하려고 한다. 색의 종류는 K개, M명의 일꾼이 있으며, 각 일꾼마다 좋아하는 색의 목록이 있다. 색을 칠할 수 있는 방법은, 길이 M의 연속된 구간과 구간의 첫 시작점을 칠할 일꾼을 한 명 골라, i번째 칸은 (i+S) mod M번 일꾼이 칠하도록 하는 것이다. 이때 색칠해야 하는 칸의 색을 그 일꾼이 좋아해야 ..