구사과

Min-plus convolution두 수열 $A = [a_0, a_1, ..., a_n]$, $B = [b_0, b_1,..., b_m]$ 이 있을 때 $c_k = \min_{k = i + j}(a_i + b_j)$ 를 구하는 것을 min-plus convolution이라고 한다. 저걸 $\max$ 로 바꾸면 max-plus convolution이다. min plus convolution은 3sum이나 apsp에서 오는 reduction은 없지만, 아직 subquadratic algorithm이 알려지지는 않은 상태 (cite: https://browse.arxiv.org/pdf/1702.07669.pdf).수열이 convex하다는 것을, $a_{i+1} - a_i$ 가 단조증가 한다는 것으로 정의한다..

IOI 2023 Day 2 대회가 종료되었다. 한국 학생들의 최종 성적은 다음과 같다. 박상훈, 43 / 60 / 65.5 / 31 / 100 / 54, 353.5점, 22등 (금메달) 이동현, 52 / 70 / 65.5 / 31 / 100 / 16, 334.5점, 28등 (금메달) 이성호, 43 / 40 / 61 / 23 / 65 / 35, 267점, 58등 (은메달) 반딧불, 43 / 60 / 65.5 / 14 / 65 / 16, 263.5점, 62등 (은메달) 금메달 2개, 은메달 2개로 평균 이상의 성적을 거두었으며, 작년과도 동일한 성적이다. 축하합니다! Day 1은 전례가 없이 어려웠는데, Day 2도 만만치 않게 어려운 문제들이 나왔다. 2018 Day 2와 유사한 결과가 나왔으니, 전례는 ..

(9/5 23:27 - 다 썼습니다) IOI 2023 Day 1 대회가 종료되었다. 올해 대회의 개최지는 헝가리로, 한국 팀은 2019년 이후 처음으로 현지에서 오프라인으로 대회를 진행하고 있다. 한국 학생들의 성적은 다음과 같다. Day 1 기준이고, Day 2 점수를 감안하지 않았음을 유념하라. 이동현, 52 / 70 / 65.5, 187.5점, 29등 반딧불, 43 / 60 / 65.5, 168.5점, 33등 박상훈, 43 / 60 / 65.5, 168.5점, 33등 이성호, 43 / 40 / 61, 144점, 56등 모든 학생들의 성적이 금메달 / 은메달의 경계선에서 멀지 않아서 Day 2의 결과가 매우 중요할 것으로 보인다. 한국 학생들은 매년 Day 2 결과가 더 좋은 편이다. Day 2에서 ..