Problem Solving
-
BOJ 16793 CollapseProblem Solving/Solution Sketch 2023. 2. 1. 10:20
JOI Open Contest 2018 #3 崖崩れ(Collapse) 문제 설명 정점 $1$부터 정점 $N$까지 $N$개의 정점이 있다. $i$번째 날에는 하나의 간선을 추가하거나 삭제한다. 다음과 같은 쿼리가 주어진다. $W$ $P$ : $W$번째 날에 $P$ 이하의 정점과 $P + 1$ 이상의 정점을 서로 잇는 간선을 모두 삭제했을때, 정점들의 총 컴포넌트의 수를 구하여야 한다. Solution 정점들의 컨포넌트를 관리하는 대표적인 방법으로는 Union & Find가 있다. 그러나, Union & Find는 간선을 추가된 순서의 역순으로만 삭제할 수 있다. 또한, 구간 $[k, k+1]$을 포함하는 모든 간선을 삭제할 경우 최악의 경우 $O(C)$이므로시간이 매우 오래 걸린다. 전체 일수를 R개씩 쪼..
-
BOJ 19933 Comparing PlantsProblem Solving/Solution Sketch 2023. 2. 1. 09:59
Comparing Plants (IOI 2020 Day 1 #1) 서브태스크를 통해 순차적인 접근이 가능한, 풀면서 즐거웠던 문제이다. 문제 설명 $n$개의 식물이 원형으로 배치되어 있다. 각 식물의 높이는 전부 다르다. 식물의 정확한 키는 알 수 없지만, 다른 식물들과의 상대적 높이는 알 수 있다. 구체적으로, 모든 식물에 대해서 자신과 시계방향으로 $k-1$개의 식물 중 자신보다 큰 식물의 개수 $r_i$가 주어진다. 쿼리로 두 개의 식물이 주어졌을 때, 두 식물의 키를 비교하여라. 만약 비교할 수 없다면 0을 리턴한다. Subtask #1 $k=2$인 경우, 모든 식물에 대하여 양옆의 식물과 직접적으로 키를 비교한 결과가 주어진다. 쿼리 $(x, y)$에 대해서, $x, x+1, ... , y$ 또..
-
Baltic Olympiad in Informatics 2022 Day 1 연습Problem Solving/Solution Sketch 2023. 1. 23. 20:00
1월 22일 오전 4시부터 9시까지 BOI 2022 Day 1을 돌았다. A를 빠르게 밀고, B를 뻘짓처음으로 template를 써서 구현하다가 30분 동안 컴파일 에러를 고치고, C의 풀이를 한시간 반만에 내고 4시간만에 올솔...... 하는 줄 알았으나, 관찰 하나를 잘못해서 결국 셋이 끝난 9시 53분경에 AC를 받았다.(5시간 53분) OI 셋을 오랜만에 돌았지만, 역시 OI 문제들이 제일 영양가 있다. 사고를 깊게 해야하고, 서브태스크를 통해 단계적인 관찰을 할 수 있다. A - Art Collections 인터렉티브 문제이다. 1부터 N까지의 순열을 publish 함수에 넣으면 inversion의 개수를 리턴할 때, 실제 순열을 구하라는 문제이다. publish 함수는 최대 N회까지 호출할 수..
-
210903, 210912 팀 연습Problem Solving 2021. 9. 16. 14:57
9월 3일과 9월 12일에 첫 / 두 번째 ICPC 팀 연습을 진행했다. 팀원은 김세린(나)(Codeforces), 이온조(Codeforces, IOI), 임성재(Codeforces, IOI)이다. 초반에는 온조가 ABCD, 내가 EFGH, 성재가 IJK를 잡고 풀기로 했다. (알고보니 난이도순이었다.) 온조가 ABC를 빠르게 밀고, 내가 G를 뇌절하면서 민 다음에 F를 밀고, 성재가 D를 밀었다. E는 내가 잡고 풀었는데, 더러운 구현 문제라 오래 걸렸다. 그동안 온조가 H, 성재가 J를 잡고 있었고, 나는 E를 푼 다음에 I를 잡았고, 더 이상 아무도 풀지 못했다. 난이도 분포도 좀 별로고, 티어를 까보니 난이도순이어서 번호순으로 자른게 실착이었던 것 같다. 문제가 13문제로 상당히 많았다. 지난번에..
-
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..