알고리즘 공부방

문제 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번 일꾼이 칠하도록 하는 것이다. 이때 색칠해야 하는 칸의 색을 그 일꾼이 좋아해야 ..

https://apio2019.ru/https://oj.uz/problems/source/389https://koosaga.com/232 내가 참가한 첫번째 apio 대회이다. 대회 결과는... 30점으로 매우 참혹한 점수가 나왔다.나는 대회시간에 device 를 읽고 어려운 수학문제라 판단하여 기본적인 부분점수만 긁고 풀지 않았는데, 이것이 가장 쉬운 문제였다. 대신 나는 마지막 문제였던 lamps에 모든 시간을 쏟아부었고, 결국 완벽한 풀이를 찾은 후 2D segment tree 구현, 경로압축까지 구현을 끝냈는데 MLE가 나서 결국 이것도 섭태밖에 긁지 못했다. 나중에 다시 풀어보니 경로압축 없이 fenwick + dynamic segment tree 하나만 있어도 AC가 나왔다...이번 년도의 문..

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) 의 상..