Eau de Cologne
Yukicoder No. 114 먼 미래 문제 링크 문제 SRM 10000이 열린 것도 옛날이야기. 여기서는 대회의 Div2 Easy 문제를 소개하려고 한다. 문제 간단히 말하면, 방향이 없고 가중치가 붙어있는 그래프가 주어진다. 정점 중 몇 개는 "중요"한 점이다. 모든 중요한 점을 연결하는 부분 그래프 중 간선 가중치 합이 최소가 되는 것을 구하고 싶다(이 그래프는 트리이다). 그때의 가중치 합을 출력하는 문제. 입력 자세한 입력 형식은, 원문을 확인해주세요. 입력의 1번째 줄에는 정점 수 $N$, 간선 수 $M$, 중요한 정점 수 $T$가 주어지고, 다음 $M$ 개의 줄에 $3$개의 정수 $a_i$, $b_i$, $c_i$가 정점 $a_i$와 정점 $b_i$를 가중치 $c_i$로 잇는다는 의미로 주..
Yukicoder No. 95 Alice and Graph 문제 링크 문제 Alice는 생일 선물로 방향성이 없는 그래프를 받았습니다. 그리고 평소처럼 그래프를 가지고 게임을 합니다. 그래프는 $N$ 개의 정점이 있고, $1$번부터 $N$번까지 번호가 붙어있으며, $k$번 정점에는 $2^{k-1}-1$ 개의 동전이 있습니다. 게임을 시작할 때, Alice는 $1$번 정점에 있습니다. $2^{1-1}-1=0$이기 때문에, $1$번 정점에는 동전이 없습니다. 그리고 Alice는 최대 $K$번 이동할 수 있습니다. 각 이동에서, Alice는 간선을 따라 인접한 정점으로 이동할 수 있고, 정점에 있는 동전을 수집할 수 있습니다. (주: 같은 정점을 두 번 방문하는 경우에도, 동전은 한 번만 수집할 수 있습니다...
Yukicoder No. 93 페가수스 문제 링크 문제 나오키 군은 $N \times N$격자의 $N$개의 "비마"(飛馬)라 불리는 신기한 말을 가지고 있습니다. "비마"는 쇼기의 비차(飛車)와 계마(桂馬)의 움직임을 합친 말입니다. (각주: 비차는 상하좌우로 원하는 만큼 이동할 수 있는 말이며, 계마는 앞으로 두 칸, 왼쪽 혹은 오른쪽으로 한 칸 움직일 수 있는 말입니다.) 어느 날 말을 배치하던 중에, "서로를 잡을 수 없도록 $N$개의 비마를 놓을 수 있는 방법"이 있다는 것을 발견했습니다. 이 조건을 만족하는 배치의 경우의 수를 $10^9+7$로 나눈 나머지를 구하는 프로그램을 작성해주세요. 단, 각 말의 구분은 없고, 모든 말은 위쪽 방향을 가리키고 있습니다. 입력 $N \ (1 \le N \l..
Yukicoder No. 67, 68 흔한 막대 자르기 문제 문제 링크 (1) No. 67 문제 링크 (2) No. 68 문제 유우키씨는 $N$ 개의 막대를 가지고 있고, $i$번째 막대의 길이는 $L_i$입니다. 막대는 (길이를 나누는 방향으로) 자유롭게 자를 수 있고, 연결하는 것은 불가능합니다. 유우키씨는 길이가 같은 막대를 $K$ 개 만들고 싶습니다. 만들 수 있는 $K$ 개 막대의 길이로 가능한 최댓값을 구하는 프로그램을 작성해주세요. 입력 입력 형식은 본문을 참고해주세요. No. 67 $1 \le N \le 200000 = 2 \times 10^5$ $1 \le L_i \le 1000000000 = 10^9$ $1 \le K \le 1000000000 = 10^{10}$ No. 68 이 문제는..
Yukicoder No. 54 Happy Hallowe'en 문제 링크 문제 오늘 할로윈을 맞아 타로군은 이웃에 사탕을 받으러 가기로 했습니다. 이웃에는, 타로군의 집 이외에 $N$ 채의 집이 있습니다. $i$번째 집에 가면 사탕을 $V_i$ 개 받을 수 있습니다. 이웃 친구와 공평하게 사탕을 나눠 가지기 위해서 이미 사탕을 $T_i$ 개 이상 가지고 있으면, (해당 집에서는) 사탕을 하나도 받을 수 없습니다. 타로군이 처음에 사탕을 하나도 가지고 있지 않고, 주위 집을 원하는 순서로 방문할 수 있을 때, 타로군이 받을 수 있는 사탕의 최댓값을 구해주세요. 같은 집은 $1$번 밖에 방문할 수 없습니다. 입력 $1$번째 줄에, 이웃의 집의 수 $N \ (1 \le N \le 10000)$이 주어집니다. 다..
Yukicoder No. 31 악의 믹스 주스 문제 링크 문제 믹스 주스가 다 떨어졌습니다. 믹스 주스의 원재료표시는, 차례대로 과일 $1$, 과일 $2$, $\cdots$, 과일 $N$입니다. 각 과일의 100% 주스를 섞어서 믹스 주스를 $V$리터 만들려고 합니다. 100% 과일 $k$ 주스는 $1$리터들이 한 팩에 $C_k$엔입니다. $V$ 리터 믹스 주스를 원재료표시의 변경 없이 만들기 위한 최소 비용을 구하는 프로그램을 작성해주세요. 즉, 믹스 주스에 대해서 과일 $k$가 들어간 비율 $p_k$는 $p_1 \ge p_2 \ge \cdots \ge p_N$이 되어야 합니다. 또한, 사용하지 않는 과일이 있어서는 안 됩니다. $1$리터 팩을 사서, 그 일부만 사용하는 것도 가능합니다. 입력 $1$번..