구사과

대충 이 노트 의 끝자락에서 한 얘기를 정리했다. 그래프가 2-edge-connected 라고 가정하자. (그렇지 않다고 하더라도 코드가 크게 바뀌지 않는다) 알고리즘은 재귀적이다. 그래프 $G$ 의 DFS 트리에 대해서, 특정 서브트리의 노드를 모두 3-connected-component로 바꿔주는 알고리즘이 존재하고, 이 알고리즘을 bottom-up 으로 호출하면서 "서브트리의 답을 합쳐주면" 된다. 2-connected 인 경우를 예시로 생각해 보자. 서브트리를 컴포넌트로 분할하는 알고리즘이 있다면, bottom-up 알고리즘은 절선으로 연결되어 있지 않으며 루트를 포함하는 컴포넌트들을 가져온 후 이들을 합쳐주면 된다. 3-connected 의 경우에는 컴포넌트 하나만 가져올 수는 없으나, 대신 D..

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에서 ..

Algorithmic Engagements 2021. Koszulki 수열을 역순으로 정렬한 후 값이 $a_k$ 이상인 수를 출력하면 됩니다. POI 2019/2020. Najmniejsza wspólna wielokrotność 최소공배수가 $R - L$ 에 대해 지수적으로 커져서 탐색해야 할 쌍이 많지 않다는 사실을 사용합니다. $R - L = 1$ 인 경우, 최소공배수는 그냥 두 수의 곱입니다. $X(X+1) = M$ 을 만족하는 $X$ 가 존재한다면, $X, X + 1$ 을 출력하면 됩니다. 이 경우는 따로 처리합니다. 이차 방정식을 풀거나 이분 탐색을 하시면 됩니다. $R - L \geq 2$ 인 경우, 최소공배수는 적어도 $L(L+1)(L+2) / 2$ 이상입니다. 고로, $L \leq 2 \..

2023년 정보화진흥원 역량강화 교육 내용을 바탕으로 작성합니다. AC로 검증 못한 풀이들이 있어 주의를 요합니다. 2차 교육 B: L과 R의 중간 지점을 기준으로, 왼쪽에 있다면 R+1에 갈 필요가 없고, 오른쪽에 있다면 L-1에 갈 필요가 없다. 따라서, L과 R 중 하나를 고려할 필요가 없다. L을 고려하지 않고 문제를 해결하고, 반대의 경우는 대칭적으로 해결한다. R이 존재하지 않을 때 한 사람이 최대로 이동하는 거리 및 그 때의 총 이동 거리를 전처리해 두면, 사람이 있는 곳과 R이 주어졌을 때의 cost를 O(1)에 구할 수 있다. 이 때, 이 cost는 monge function이고, 2023 선발고사에 나왔던 “팀 만들기”의 60점 풀이를 그대로 사용하면 해결할 수 있다. D: $S < X..

티스토리 렌더링 문제로 수식이 많이 깨진다. 일단 깨진 형태로 올려두지만 쉽게 볼 수 있는 PDF를 첨부한다. PDF를 보는 것을 추천한다. Chapter 4. $\boxdot$ 연산자의 빠른 구현 현재 우리의 알고리즘이 $O(N^5)$ 인 이유는 다음과 같다: $\boxdot$ 연산자가 $O(N^3)$ 에 구현됨 $\boxdot$ 연산자를 $O(N^2)$ 번 호출함 잠시 $\boxdot$ 연산자의 실제 이름을 짚고 넘어가자면, 논문에서는 위 연산자가 unit-Monge matrix-matrix distance multiplication 라는 이름으로 소개되었다. Part 1에서는 괜히 글이 어렵다는 인상을 줄 것 같아서 의도적으로 언급하지 않은 이름이다. 이제부터는 (순열의) unit-Monge 곱 이..

티스토리 렌더링 문제로 수식이 많이 깨진다. 일단 깨진 형태로 올려두지만 쉽게 볼 수 있는 PDF를 첨부한다. PDF를 보는 것을 추천한다. 이번 글에서는 다음과 같은 쿼리를 수행하는 자료 구조에 대해 다룬다: 길이 $N$ 의 수열 $A$ 와 $Q$ 개의 쿼리 $1 \le i \le j \le N$ 가 주어질 때, $A[i], A[i + 1], \ldots, A[j]$ 의 최장 증가 부분 수열 (Longest Increasing Subsequence, LIS) 를 계산하라. LIS 문제의 경우 동적 계획법으로 해결할 수 있는 가장 기초적인 문제 중 하나로, 수학적으로 여러 의미를 가지기 때문에 변형된 문제들이 다방면으로 연구되고 있다. 위와 같은 쿼리 문제는 다들 자료 구조 문제를 고민해 보다가 한번쯤 ..

문자열의 부분문자열에 대한 복잡한 문제를 풀 때 Suffix Array와 같은 접미사 구조 는 아주 강력한 도구가 된다. SCPC 2021 3번, 서울 리저널 2022 H 등 여러 중요한 대회에서도 이러한 접미사 구조를 응용한 문제들이 정말 많이 나온다. 한국에서 많은 사람들이 알고 있는 접미사 구조로는 Suffix Array 가 있다. Suffix Array는 모든 문자열의 접미사를 정렬한 순열로, 흔히 부분문자열 탐색 쿼리를 빠르게 처리하거나 두 접미사의 LCP를 구할 때 많이 쓰인다. 문자열 접미사 구조 중 알려진 자료구조는 크게 Suffix Array, Suffix Tree, Suffix Automaton 이 있는데, 한국에서는 Suffix Array만이 알려져 있는 편이고, 그 외 다른 자료구조..

Codeforces에 올린 글을 보관 목적으로 블로그에도 올립니다. Yesterday I participated in a local contest involving a problem about Monge arrays. I could&#39;ve wrote some d&c optimization, but I got bored of typing it so I copypasted maroonrk&#39;s SMAWK implementation to solve it. Today, I somehow got curious about the actual algorithm, so here it goes. 1. Definition I assume that the reader is aware of the concept o..