Eau de Cologne

https://www.acmicpc.net/problem/2437 2437번: 저울 하나의 양팔 저울을 이용하여 물건의 무게를 측정하려고 한다. 이 저울의 양 팔의 끝에는 물건이나 추를 올려놓는 접시가 달려 있고, 양팔의 길이는 같다. 또한, 저울의 한쪽에는 저울추들만 놓 www.acmicpc.net 풀이 이후 작성 https://www.acmicpc.net/problem/24762 24762번: Ticket Completed? The first line of input contains two integers $N$ ($2 \leq N \leq 10^5$), which is the number of cities, and $M$ ($0 \leq M \leq 10^6$), which is the number..

이번 주차도 난이도가 낮은 문제로 준비했습니다. https://www.acmicpc.net/problem/1548 1548번: 부분 삼각 수열 세 수 x, y, z가 x+y>z, x+z>y, y+z>x의 관계를 만족하면, 세 수는 삼각관계에 있다고 한다. 마찬가지로 길이가 N인 수열 B(b[0], b[1], ..., b[n-1])의 모든 b[i], b[j], b[k]가 삼각관계에 있으면 이 수열은 삼각 www.acmicpc.net 풀이 더보기 세 수 $a \le b \le c$가 삼각관계에 있는지 아닌지를 확인하기 위해서는 $a + b > c$인지 아닌지만 확인하면 됩니다. 왜냐하면, $c$는 $a$와 $b$이상이고 $c+a$와 $c+b$는 모두 $c$보다 크기 때문에 $c+a>b$와 $c+b>a$는 항..

이번 주차는 쉬어가는 주차로 준비했습니다. 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$ 막대기가 들어왔을 때, ..