Eau de Cologne

연습 (1) 에서는 solved.ac 기준 G5...G1 문제들을 다루고, 연습 (2)에서는 solved.ac 기준 P5...P3 문제들을 다룹니다. https://www.acmicpc.net/problem/1885 1885번: 비부분수열 수열에서 몇 개의 수를 순서대로 골라 만들 수 있는 수열을 부분수열이라고 한다. 예를 들어 수열 S = [1, 5, 3, 2, 5, 1, 3, 4, 4, 2, 5, 1, 2, 3]에서 첫 번째, 다섯 번째, 일곱 번째, 열 번째 수를 고르면 부 www.acmicpc.net 비고: 부분수열 $p$의 모든 원소도, $1$ 이상 $k$ 이하로 이루어져야 합니다. 풀이 더보기 $p$가 $S$의 부분수열이라면 $p$의 모든 문자는 차례로 $S$에 대응됩니다. 이를 판단하는 방법..

https://www.acmicpc.net/problem/22988 22988번: 재활용 캠페인 첫 번째 용기와 두 번째 용기를 가져가서 용량이 $\left(0+1+\frac{13}{2}\right)$㎖ $=$ $7.5$㎖ 남은 용기를, 세 번째 용기와 네 번째 용기를 가져가서 용량이 $\left(2+3+\frac{13}{2}\right)$㎖ $=$ $11.5$㎖ 남은 용 www.acmicpc.net 풀이 더보기 다음과 같은 관찰을 이용합니다. 임의의 수 $3$개를 골라서 $X$로 만들 수 있다. 두 수를 합치면 수에 관계 없이 $X/2$이상이 되고, 또 다른 수와 합치면 $X$가 됩니다. 그렇기 때문에, $X$를 최대한 많이 만드는 절차는 다음과 같습니다. 이미 존재하는 $X$를 제외한다. $2$개씩 ..

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)$の$..