Eau de Cologne
문제 방향과 가중치가 있는 그래프 $G = (V, E, w: E \rightarrow \mathbb{R})$가 있습니다. 여기서 사이클의 평균 가중치란 사이클을 구성하는 간선 가중치의 평균을 의미합니다. 그래프 $G$에 있는 모든 사이클 중 제일 작은 평균 가중치인 최소 사이클 평균 가중치는 무엇일까요? 엄밀히 작성하면 다음과 같습니다. 사이클이란 정점의 수열 $c = e_1, e_2, \cdots, e_k$을 의미하며, 다음 조건을 만족해야합니다. $e_i$의 끝 정점은 $e_{i+1}$의 시작 정점이어야 하며, $e_1$의 시작 정점과 $e_k$의 끝 정점은 같아야 합니다. 사이클 $c = e_1, e_2, \cdots, e_k$의 평균 가중치 $\mu(c)$는 다음과 같이 정의됩니다. $\mu_G(..
oj.uz / acmicpc.net 문제 Anna, Bruno, D-taro가 게임을 진행합니다. 게임을 시작할 때, Anna는 $1$ 이상 $2000$ 이하의 정수 $m$ 하나를 선언합니다. 이후 게임은 $Q$개의 라운드로 구성되며, 각 라운드는 다음과 같이 진행됩니다. D-taro가 Anna에게 정수 $A$를 줍니다. Anna는 $s, t$를 기계에 입력합니다. $s$와 $t$는 각 원소가 $0$ 혹은 $1$이어야 하고, 두 배열의 길이가 같아야 하며, 길이가 $1$ 이상 $m$ 이하여야 합니다. $s$와 $t$를 리플 셔플해서 얻은 배열 $u$를 Bruno에게 보냅니다. $s$와 $t$를 리플 셔플한 결과가 $u$라는 것은, $u$에 있는 수를 두 그룹으로 나눴을 때 첫째 그룹은 $s$, 둘째 그룹..
링크: https://yukicoder.me/problems/no/137 문제 요약: $A_1$원, $A_2$원, $\cdots$, $A_N$원짜리 동전이 있습니다. 이 동전을 적당히 사용해서 합이 $M$원이 되도록 만드는 되는 경우의 수를 $1\,234\,567\,891$로 나눈 나머지를 구하세요. 하나 이상의 동전의 개수가 다른 경우 다른 경우로 셉니다. 제한 시간 제한: 5초 / 메모리 제한: 512MB $1 \le N \le 50$ $1 \le M \le 10^{18}$ $1 \le A_1 < A_2 < \cdots < A_N \le 500$ 풀이 더보기 $ \sum c_NA_N = M$이 되는 $0$ 이상의 수로 이루어진 $(c_1, \cdots, c_N)$ 순서쌍의 개수를 세는 문제입니다. $..
문제: https://www.acmicpc.net/problem/16696 풀이: 더보기 BFS를 하듯이 백트래킹을 하면 됩니다. 빠른 백트래킹을 위해서, 비트마스킹을 썼습니다. $x$와 $x$아래로 $i$칸 내려간 상태를 표시하기 위해서는 $s \ \mid \ (s > > i)$ 를 사용할 수 있습니다. 또한, 중복된 상태를 방문하지 않기 위해서 정렬을 한 이후, 중복된 원소를 제거하는 방식으로 구현했습니다. 코드: https://www.acmicpc.net/source/share/35607263092d4ea78f1b169dbba60b10 문제: https://www.acmicpc.net/problem/11851 풀이: 미작성 문제: https://www.acmicpc.net/problem/4181 풀..
사전 지식 Lazy Segment Tree의 구현 Atcoder Library의 Lazy Segment Tree 설명: https://atcoder.github.io/ac-library/production/document_en/lazysegtree.html 레이지 세그먼트 트리는 타입 $S$와 $S \rightarrow S$로 가는 함수들의 부분집합 $F$가 존재해서, 각 원소가 $S$ 타입인 배열에서 다음 일을 할 수 있습니다. 배열의 연속된 구간과 $f \in F$가 주어지면, 연속된 구간의 각 원소를 $s_i$에서 $f(s_i)$로 바꿉니다. 배열의 연속된 구간$[s_l, \cdots, s_r]$이 주어지면, $s_l \circ \cdots \circ s_r$ 을 구합니다. 여기서 연산 $\circ..
D5~ 문제들을 작성합니다. https://www.acmicpc.net/problem/19297 19297번: Logistical Metropolis 첫 번째 줄에 두 정수 $N$, $M$($1 ≤ N ≤ 100\,000$, $N-1 ≤ M ≤ 300\,000$)이 공백 하나로 구분되어 주어진다. 다음 $M$개 줄의 각 줄에는 건설 가능한 워프 게이트의 정보를 나타내는 세 정수 $x$, $y$, $c$($ www.acmicpc.net 풀이 더보기 처음에 Minimum Spanning Tree를 만듭니다. 이 이후에 무조건 사용되는 간선(여기서는 i번과 모두 연결된 간선)이 $k$개 정해졌을 때, 이 계산을 $\tilde{O}(k)$ 안에 하는 문제입니다. 각 정점마다 정점 차수만큼의 간선을 지정하고, 모..