serin-ch serin-ch

전체 글

• 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)$가 커버하는 범위에서 이미 등장한 적 있다면, 해당 문자와 같은 문자로 생각하여 비교한..

  Read More

• BOJ 17665 Triple Jump

  Problem 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] ..

  Read More

• BOJ 16793 Collapse

  Problem 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개씩 쪼..

  Read More

• BOJ 19933 Comparing Plants

  Problem 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$ 또..

  Read More

• 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회까지 호출할 수..

  Read More

• BOJ 19558 Joker

  Problem Solving/Solution Sketch 2023. 1. 23. 10:38

  BOI 2020 #C Joker 오랜만에 글을 쓴다. Summary 그래프가 주어진다. ($1

  Read More

• 알고리즘 과외 합니다.

  카테고리 없음 2022. 8. 29. 17:45

  https://justicehui.github.io/teach/serin/ 알고리즘 과외 합니다 * 블로그 관리자가 하는 과외가 아닙니다. ## 알고리즘 과외 합니다 안녕하세요. KAIST 수리과학부 소속 김석표입니다. 아래 링크에서 제 프로필을 확인할 수 있습니다. {% include judge_profile.html boj_id justicehui.github.io 급하게 과외를 구하게 되어서 개인 블로그에도 작성합니다.

  Read More

• 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문제로 상당히 많았다. 지난번에..

  Read More