Eau de Cologne
https://www.acmicpc.net/problem/8031 8031번: Weaker Goldbach In the year of 1742 C. Goldbach wrote in his letter to L. Euler that according to him each integer n > 5 was the sum of three prime numbers (a prime number is an integer n > 1, which has only two positive, integer divisors: 1 and n.). Euler answered, that www.acmicpc.net 풀이 더보기 $2 \times 10^9$이하의 수에 대해, 다음이 성립합니다. $10$ 이상의 짝수는 홀수인 서로 다른..
적당한 난이도의 (solved.ac기준 G5..G1) 문제를 골라서 하루에 한 문제, 일주일에 7문제 정도를 풀고, 풀이를 작성합니다. https://www.acmicpc.net/problem/20131 참고: https://www.acmicpc.net/problem/23285 20131번: 트리 만들기 정점이 N개가 있는 트리가 있고 각 정점들은 1부터 N까지 번호가 매겨있다. 해당 트리로부터 (N-2)개의 양의 정수로 이루어진 수열 하나를 다음과 같은 과정을 통해서 만들 것이다. 차수가 1인 정 www.acmicpc.net 풀이 더보기 이 수열을 Prüfer Sequence라고 하고, 다음과 같은 중요한 성질을 만족합니다. 이 수열에서 $a$가 $C_a$번 등장하면, 트리에서 정점 $a$의 차수는 $..
No. 1873 Bracket Swapping 문제 링크 제한 시간 제한: 2초 메모리 제한: 512MB 문제 올바른 괄호 문자열 $S$와 음이 아닌 정수 $K$가 주어집니다. $S$에 대해 다음 조작을 $K$번 반복한 이후의 $S$가 올바른 괄호 문자열이 되는 경우의 수를 $998244353$으로 나눈 나머지를 구해주세요. $1 \le i < j \le |S|$를 만족하는 정수 $(i, j)$를 고른다. $S$의 $i$번째 문자와 $j$번째 문자를 교환한다. 단, 어떤 정수 $l$ ($1 \le l \le K)$가 존재해서 $l$번째 고른 $(i, j)$가 다른 경우, 또한 그 경우에 한해서 두 조작방법을 다르다고 합니다. 올바른 괄호 문자열의 정의 다음을 만족하는 괄호 문자열을 올바른 괄호 문자열이라..
問題: https://yukicoder.me/problems/no/1857 $X$が正の整数の時、$E[X] = P(X \ge 1) + P(X \ge 2) + P(X \ge 3) + \cdots$あ成立します。 $P(X \ge k)$のためには、最初の$k-1$回引いた品物が全部違う必要があります。 最初の$k-1$回で決めた順番に品物を引く確率は簡単にそれぞれの積に計算できます。 最初の$k-1$回で順番を決める方法は$k-1$個の品物を決めたあと順番を決めるのでできます。 $P(X \ge k) = (k-1)!\times\sum_{S \subset \{1, \cdots, n\}, |S| = k-1} \left(\prod_{i \in S} p_i\right) $になります。 $\prod_{1 \le i \le N} (1+p_ix) $の$..
최빈값 문제에 대한 고찰 중복을 허용하는 집합인 multiset $S$에 대해, $S$에서 $x$가 등장하는 횟수를 ${\rm freq}_S(x)$라고 씁시다. 모든 $x \in S$에 대해서, ${\rm freq}_S(x) \le {\rm freq}_S (a)$를 만족하는 경우에, $S$를 최빈값이라고 부릅니다. $S$의 최빈값은 여럿일 수는 있지만, 최빈값이 등장하는 개수인 $m$은 유일합니다. 우리는 다음 문제에 관심이 있습니다. 배열 $A$가 주어졌을 때, 배열의 $i$번째부터 $j$번째까지 원소인 $A[i:j]$의 최빈값을 효율적으로 구할 수 있을까? 이 글에서는 다음 주제에 대해서 다룹니다. 배열 $A$의 최빈값을 찾는 방법 특수한 경우를 효율적으로 해결하는 방법 ${\rm freq}_S(x)..
Yukicoder No. 119 여행 문제 문제 링크 문제 $N$ 개의 나라가 있습니다. 나라는 $0$번부터 $N-1$번까지 번호가 붙어있습니다. A군은 $N$개의 나라 중 방문하고 싶은 나라를 골랐습니다. A군은 반드시 번호가 작은 나라부터 차례로 방문을 합니다. 여행사에는 각 나라별로 $1$개씩의 여행 패키지가 있습니다. 여행 패키지에 참여하는 게 좋을 때도 있지만 자유도가 줄어들어서 싫을 때도 있습니다. 여행 패키지에 참여할 때와, 참여하지 않을 때의 만족도가 정해져 있습니다. 또한, 여행사 직원의 말은, "한 나라의 여행 패키지에 참여하면, 다른 나라의 여행 패키지에도 참여해야 한다." 같은 조건이 있는 경우도 있다고 합니다. 예를 들면, $x$번 나라의 여행 패키지에 참여하면, $y$번 나라의 ..