Eau de Cologne
이번 주차는 쉬어가는 주차로 준비했습니다. https://www.acmicpc.net/problem/12430 12430번: 생존자 (Large) 당신은 무인도에 조난당했다. 다행히 음식이 들어있는 상자를 하나 챙길 수 있었지만, 풀 한 포기 보이지 않는 돌 섬인데다 낚시를 할 방법이 없어서 추가적인 음식 공급은 어려운 상황이다. 잠 www.acmicpc.net 풀이 더보기 음식을 먹는 순서가 $s_1, s_2, s_3, \cdots, s_K$라고 합시다. 우리는 인접해서 음식을 먹는 $a = s_i$ 번째와 $b = s_{i+1}$ 번째 음식에 집중할 것입니다. $s_{i-1}$ 번째 음식까지 먹었을 때 지난 시간을 $X$ 분이라고 합시다. $a$와 $b$ 순서대로 음식을 먹었을 때 조건은 $a$번째 ..
이번 주차는 쉬어가는 주차로 준비했습니다. https://www.acmicpc.net/problem/12875 12875번: 칙령 예제 1의 경우에 왕국에는 세 명의 사람들이 살고 있다. 1과 2는 친구이고, 2와 3은 친구이다. 가능한 방법 중 돈을 가장 많이 가진 사람과 적게 가진 사람의 차이의 최댓값은 20이다. 사람 1이 100원 www.acmicpc.net 풀이 더보기 주어진 그래프가 연결그래프가 아닌 경우에는 다른 연결성분의 사람이 가진 돈의 양을 임의로 정할 수 있기 때문에 차이가 무한대가 될 수 있습니다. 연결그래프인 경우에는 답이 그래프의 지름(두 정점 사이의 최단거리 중 최댓값)에다가 $d$를 곱한 값임을 증명하겠습니다. 답은 지름 $\times d$보다 작거나 같다. 두 사람 $s, ..
Polynomial 관련 라이브러리입니다. Polynomial은 $\sum_{i=0}^d a_i x^i$로 표현되며, $a$에 해당하는 길이 $d+1$의 배열을 내부에 가지고 있습니다. Polynomial은 Field $F$위에서 정의되며, $\vec{a}$와 $\vec{b}$의 convolution을 계산하는 함수를 제공해야합니다. 아래에서, convolution을 계산하는 함수의 시간복잡도가 길이가 $d$인 경우 $O(d \log d)$라고 가정합니다. 생성자 인자가 없으면 빈 다항식을 생성합니다. vector를 인자로 주는 경우, $i$번째 원소를 $a_i$로 하는 다항식을 생성합니다. int deg(), void set_degree (int deg) 차수에 관한 함수입니다. $f = 0$은 차수 ..
연습 (1) 에서는 solved.ac 기준 G5...G1 문제들을 다루고, 연습 (2)에서는 solved.ac 기준 P5...P3 문제들을 다룹니다. https://www.acmicpc.net/problem/2242 2242번: 삼각형 만들기 N(3 ≤ N ≤ 40)개의 막대기들이 있다. 각각의 막대기들은 길이가 서로 같은 수도 있고, 서로 다를 수도 있다. 이러한 막대기들을 연결하여 하나의 삼각형을 만들려고 한다. 이때 사용하지 않는 막 www.acmicpc.net 풀이 더보기 두 변의 길이를 고정하면, 나머지 한 변의 길이는 쉽게 알 수 있습니다. 그렇기 때문에, $i, j$를 변으로 하는 삼각형을 만들 수 있는지를 $D_{i, j}$로 정의합니다. 이렇게 되면, 새로 $x$ 막대기가 들어왔을 때, ..
연습 (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$개씩 ..