전체 글
-
BOJ 19935 Carnival TicketsProblem Solving/Solution Sketch 2021. 2. 16. 20:49
Carnival Tickets (IOI 2020 Day 1 #3) 문제 설명 - $n$가지 색의 티켓이 각 색마다 $m$개씩 존재하며, 티켓에는 각각 하나의 정수가 쓰여있다. - $k$회의 라운드 동안, 각 라운드마다 하나의 색에서 하나의 카드를 선택하여 카드에 대해 점수를 받는다. 뽑은 카드에 적힌 숫자들을 크기 순서대로 $A_{1}$, $A_{2}$, $\cdots$ , $A_{n}$이라고 하자. - 마스터 또한 카드 한 장을 뽑는다. 마스터가 뽑은 카드에 적힌 수가 $b$라고 하면, $\sum \left\vert A_{i} - b \right\vert$이 이번 라운드에 얻게 되는 점수이다. - 각 라운드가 끝날떄마다 라운드에서 사용된 카드는 버려진다. - 마스터는 각 라운드마다 점수가 최소화되도록 ..
-
BOJ 19934 Connecting SupertreesProblem Solving/Solution Sketch 2021. 2. 16. 20:09
Connecting Supertrees (IOI 2020 Day1 #2) 문제 설명 - $n$개의 정점이 있다. - 정점 $i$에서 정점 $j$로 가는 서로 다른 단순경로가 정확히 $p(i, j)$개가 되도록 그래프를 설계할 것이다. - 이를 만족하는 그래프가 존재하는지 판별하고, 존재한다면 그 중 하나를 구하여라. 존재성 판별 및 그래프 설계 일단, 조건을 만족하는 그래프가 존재하는지부터 생각해보자. 96점어치 Subtask에서는 $0 \leq p(i, j) \leq 2$이므로, $0 \leq p(i, j) \leq 2$일 때를 생각해보자. - $p(i, j) = 1$에 대한 관찰 Lemma 1. 정점 $i$에 대하여 $p(i, j) = 1$인 $j$들의 집합을 $S$라 하자. 그러면 $x, y \in..