Problem Solving/Solution Sketch
-
2020년도 대한민국 국제정보올림피아드 선발고사 풀이 (Day 2)Problem Solving/Solution Sketch 2023. 2. 4. 22:02
Day 1: https://dsstar.tistory.com/48 이어서 작성한다. Day 2 1. 마법의 다이얼(BOJ 25012) Solution 각 행에 대해, 해당 행에서 i에 다이얼이 오도록 맞추는 비용을 생각해보면, 함수의 개형은 지그재그 꼴이 된다. 다이얼이 처음 상태에서 위치한 곳의 함수값은 0, 거기서부터 시작해서 좌우로 함수의 기울기가 왼쪽으로 -1, 오른쪽으로 1인 그래프가 되고, 다른 직선과 만나게 된다면 끊기게 된다. 더 정확히 설명하자면, $s$, $e$ 사이의 그래프는 s에서 기울기가 1 증가, $\lfloor (s+e)/2 \rfloor$에서 기울기가 1 감소, $\lceil (s+e)/2 \rceil$에서 기울기가 1 감소, e에서 기울기가 1 증가한다. 기울기가 변하는 점..
-
2020년도 대한민국 국제정보올림피아드 선발고사 풀이 (Day 1)Problem Solving/Solution Sketch 2023. 2. 3. 20:12
선발고사에서 떨어진 아픈 기억이 있는 셋이다.(스코어보드상 6등) 과거의 상처를 극복하고 싶어서 2월 1일 13시 30분에 시작하는 셋을 만들었고, 2월 3일 7시 52분에 대회장에서 풀지 못했던 마지막 문제인 지름길을, 9시 6분에 마법의 다이얼과 칠하기를 다시 구현하기를 끝내며 모든 문제를 BOJ에서 AC를 받았다. 인터넷을 찾아보니 정휘님 블로그 글이 있긴 한데, 다른 블로그와 중복된 자료를 싫어하는 편이지만 세 문제의 풀이가 빠져 있어 작성한다. Day 1 1. 문자열 찾기(BOJ 25008) Solution P에 대해서 '사실상 같은' 실패함수를 만들어줄 수 있다. $i$번째로 등장하는 문자가 $fail(i)$가 커버하는 범위에서 이미 등장한 적 있다면, 해당 문자와 같은 문자로 생각하여 비교한..
-
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회까지 호출할 수..
-
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$이 이번 라운드에 얻게 되는 점수이다. - 각 라운드가 끝날떄마다 라운드에서 사용된 카드는 버려진다. - 마스터는 각 라운드마다 점수가 최소화되도록 ..