전체 글
-
BOJ 17665 Triple JumpProblem Solving/Solution Sketch 2023. 2. 1. 10:32
JOI Open Contest 2019 #1 三段跳び(Triple Jump) 문제 설명 직선 위에 $N$개의 구역이 있으며, i번 구역의 점수는 $A[i]$이다. ‘3단 점프’란, 다음의 조건을 만족하는 세 개의 구역 $(a, b, c)$의 순서쌍이다. $a < b < c$ $b - a < c - b$ 3단 점프의 점수는 $A[a]+A[b]+A[c]$, 즉 3단 점프에 속하는 세 구역의 점수의 합이다. $Q$개의 쿼리 $(l, r)$이 주어진다. 각 쿼리에서는, $l ≤ a < b < c ≤ r$을 만족하는 3단 점프 $(a, b, c)$들의 점수의 최댓값을 구하여야 한다. 필요한 관찰 다음과 같은 3단 점프 $(a, b, c)$는 의미가 없다는 것을 알 수 있다. $a < d < b$이며, $A[a] ..
-
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문제로 상당히 많았다. 지난번에..