Eau de Cologne

문제: https://www.acmicpc.net/problem/15479 문제 요약: $A$의 연속된 부분수열 중 길이가 $K$ 이상인 모든 부분수열을 구하고, 그 수열의 (작은 순으로) $K$ 번째 수를 구합니다. 그 수를 모두 모았을 때 $L$ 번째 수를 구합니다. 풀이: 더보기 $A$의 모든 값이 $0$이나 $1$인 경우 $L$ 번째 수를 구하기 위해서는 $K$ 번째 수가 $0$인 구간의 수를 세면 됩니다. $K$ 번째 수가 $0$이라는 것은 수열에서 $0$이 $K$ 개 이상 있다는 의미입니다. 이는 two-pointer를 사용하면 쉽게 구할 수 있습니다. 원래 문제를 결정문제로 바꾸기 위해서 parametric search를 사용하면 문제를 해결할 수 있습니다. 코드: https://www.ac..

문제: https://www.acmicpc.net/problem/19669 풀이: 더보기 degree가 $1$인 노드 $u$를 생각합시다. 해당 노드에 소방서를 놓는 것과 해당 노드랑 바로 인접한 간선 $v$에 소방서를 놓는 것을 생각해보면, $u$를 제외한 다른 모든 정점은 $v$에 소방서를 놓는 것이 더 가깝습니다. 만약 $v$에 소방서를 놓은 이후 길이가 $w (\le K)$인 도로를 따라 $u$로 올 수 있다면, $u$에는 굳이 소방서를 놓을 필요가 없습니다. 이 경우에는 $v$와 $K-w$ 거리 이내에 있는 소방서가 있는 것으로 충분합니다. 이 관찰을 확장해서 정점 $i$가 거리 $R_i$ 이내의 소방서를 필요로 한다고 해 봅시다. degree가 $1$ 인 노드 $u$와 길이 $w$의 도로로 인..

문제 방향과 가중치가 있는 그래프 $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 풀..