구사과

PA 2012. Mecze 두 선수가 경쟁하지 않았다는 것은, 두 선수가 항상 같은 팀에 있었다는 것과 동치입니다. 고로 각 선수가 무슨 팀에 있었는지를 크기 $M$ 의 배열에 저장하고, 배열들을 정렬한 후 중복 원소가 있는지를 체크하면 됩니다. 배열을 정렬하기 위해서는 배열간 비교가 가능한 vector 같은 자료형을 쓰거나 $M \le 50$ 이니 배열 대신 long long 자료형에 비트마스크로 저장하거나 등등의 방법이 있습니다. Petrozavodsk Winter 2022 Day 1 - Kyoto U Contest. Build The Grid 사진으로 대체합니다: 이러한 구성을 찾는 방법은 여러 가지가 있습니다. 저의 경우에는 그냥 백트래킹을 돌려서 조건을 만족하는 그리드를 찍어보고, 규칙을 찾았습..

(2023.10.20 - Def2->Def3 증명의 오류를 수정하고 Typesetting을 좀 손봤다.) 알고리즘에서 다루는 많은 문제들은 그래프 문제로 환원할 수 있는데, 일반적인 그래프에서 어떤 문제들은 효율적으로 해결이 불가능한 경우가 있다. 이러한 비효율성의 대표적인 예시는 NP-hard로, 어떠한 문제가 NP-hard일 경우 다항 시간으로 푸는 것이 아예 불가능할 가능성이 높다. 그 외에도, 최단 경로 문제와 같이 다양한 쿼리에 대해서 빠른 시간 안에 해결하는 것이 어려운 경우 등, 비효율성의 예시는 NP-hard에 한정되지 않는다. 이러한 비효율성에 당착했을 때 자주 취하는 전략은 환원한 그래프의 특수성에 의존하는 것이다. 예를 들어, NP-hard 문제들이라 하더라도 그래프가 직선, 트리, ..

2월의 Push-Relabel algorithm 관련 글에 이어서 Push-relabel에 기반한 다항 시간 MCMF 알고리즘 (Cost Scaling)에 대해서 다룰 예정이다. 이 글에서는 일반적으로 알려진 Successive Shortest Path Algorithm보다 훨씬 더 효율적인 알고리즘을 다룬다.MCMF (Minimum-Cost Maximum-Flow) 문제는 알고리즘 대회 입문서에 다 소개되어 있는 중요한 문제이다. 2월 중순에 글이 올라온 뒤, 3월 1일 Almost-Linear Time Minimum Cost Flow 가 가능하다는 사실이 알려져서 많은 화제를 모았다. 당연하지만 이론전산에서 아주 중요한 연구 결과이고, 저자들은 아마 권위있는 상 하나 정도는 수상하지 않을까 싶다. ..

Pisinger Algorithm Subset Sum 문제는, positive integer multiset S와 정수 t가 주어졌을 때, 합이 t인 S의 부분집합이 있는지를 찾는 문제이다. S의 원소 범위가 1 이상 M 이하의 정수라고 가정하자. $M$ 에 대한 dependency가 없이 풀려면 당연히 NP-hard이다. 그냥 DP를 하면 $O(n^2M)$ 이다. 각 숫자를 prefix sum으로 처리하면 $O(nM^2)$이다. Generating function으로 $O(nM \log nM)$ 에 푸는 풀이가 비교적 최근에 발견되었다. 꽤 깔끔한 $O(nM)$ 풀이를 서술 일단 첫 번째 Lemma는, 이 문제를 모든 수가 [-M, M] 인 multiset S에서 합이 1 = F[j][k + a[i]]..

그래프의 최대 유량 (Maximum Flow) 를 찾는 문제는 웬만한 알고리즘 대회 입문서에는 다 소개되어 있는 중요한 문제이다. 일반적으로 최대 유량을 찾기 위해서는 Edmonds-Karp, Dinic과 같은 알고리즘을 사용한다. 이 알고리즘의 특징은 빈 그래프에서 시작해서 유량을 증가시키는 "증가 경로" 를 찾는 것을 반복하는 식으로 작동한다는 것이다. Dinic 알고리즘은 최악의 경우 $O(V^2E)$ 에 작동하지만 실제로는 이보다 훨씬 효율적으로 작동한다. 하지만 그럼에도 선형 시간에 가까울 정도로 빠르지는 않고, 한계가 분명히 있는 알고리즘이다. 이 글에서는 Push-relabel 이라고 하는 새로운 플로우 알고리즘을 설명한다. 예전에 유량 관련 알고리즘을 정리할 때도 간략하게 설명한 적이 있는..

Algorithmic Engagements 2010. Rectangles 2 부분 직사각형의 크기가 $w \times h$ 라면, 그 둘레는 $2(w+h)$ 이고, 등장 횟수는 $(n-w+1)(m-h+1)$ 입니다. 이를 토대로 모든 가능한 경우를 나열한 후 횟수를 합해주면 됩니다. Algorithmic Engagements 2010. Coins 문자열을 수열로 변환합니다. 앞면에 대해서는 $1$ 을, 뒷면에 대해서는 $-k$ 를 적어줍시다. 이렇게 하면, 구간의 합이 $0$ 인 것과 앞면의 수가 뒷면의 수보다 $k$ 배 많이 나온 것이 동치입니다. 고로 구간 합이 0인 가장 긴 구간을 찾아야 합니다. 위 수열의 부분합 $S[i] = \sum_{i = 1}^{n} A[i]$ 를 구해줍시다. 이제 답은 $..

Result Analysis 이번 서울 리저널에서의 각 대학 별 상위 팀은 다음과 같다. 별 일 없다면 상위 3팀이 진출할 것이다. 서울대학교: FSM (World Finals 진출 확정) KAIST: DO Solve (World Finals 진출 확정) 숭실대학교: LongestPathToWF (World Finals 진출 매우 유력) 성균관대학교: iota24 (World Finals 진출 가능성 약간 존재) 고려대학교: TLE NIE TAK 서울대학교의 FSM 팀은 2020년 대회를 우승한 Let Us Win ICPC WF 팀과 동일한 멤버로 출전하였다 (김세빈, 윤교준, 이민제). 2020년에도 신입생 팀으로 ICPC Regional Champion을 차지한 팀으로, UCPC 2021, SCPC ..

작년에 쓴 인예 풀이가 도움이 되었다는 말씀을 전해 주신 분들이 몇 있었다. 이번에도 문제가 백준 온라인 저지에서 상당 부분 채점이 되기 때문에 간단히 풀이를 적어보려고 한다. 자세하게 설명할 여력이 안 되는 점에는 양해를 구한다. 일단 DFG 외에는 백준에 전부 제출해서 맞은 코드들이지만, 풀이가 틀릴 가능성도 있다. A. Best Student 여러 풀이가 있지만 내가 생각하기에 AC받기 제일 쉬운 풀이는 다음과 같다. (대회장 환경에 따라 시간 초과가 날 수도 있지만, 안 날 것 같다.) 구간을 크기 $B = 100$의 버킷 1000개로 쪼개자. 모든 $0 \le i \le j \le N / B$ 에 대해, 구간 $[iB, jB - 1]$ 에서 가장 많이 등장하는 숫자를 $O(N^2/B)$ 에 전처..

원래 한 150점 어치 풀이를 적어놓은 게 있었는데, 포맷하다가 글이 사라져서 더 이상 글을 쓰고 싶지 않았다. 그래도 아예 안 적을 수는 없으니 늦게나마 글을 작성해 본다. 문제 풀이 한 줄 요약 육각형 영역: 다각형 내부의 모든 격자점 간의 거리 합을 구하는 문제로 환원할 수 있다. 다각형의 3개의 축을 분리하여 생각하면, 각 축에 대해서 삼각분할과 비슷한 일종의 트리를 형성할 수 있고, 모든 경로가 이 트리 상의 유일한 경로로 환원됨을 관찰할 수 있다. BST에 Plane sweeping을 사용하여 이러한 트리를 빠르게 구성한 후 트리 안에서 동적 계획법을 수행할 수 있다. 밀림 점프: Cartesian tree 형태의 그래프에서 최단 경로 쿼리를 빠르게 해결하는 문제이다. 기본적으로 그래프의 Tr..

https://www.acmicpc.net/problem/19021 트리를 DFS하면서, 노드의 방문을 시작한 시점에 (, 끝내는 시점에 ) 를 붙이는 식으로 올바른 괄호 문자열을 만들어 줄 수 있습니다. 주어진 입력을 트리가 아니라 괄호 문자열이라고 생각하면 1, 2번 연산은 짝이 맞는 괄호 쌍을 추가하는 것이고 3번 연산은 짝이 맞는 괄호 쌍을 제거하는 것 으로 볼 수 있습니다. Edit Distance와 LCS의 관계처럼, 두 괄호 문자열의 최대 공통 부분 괄호 문자열을 찾아 줍시다. $T_1$ 의 모든 괄호를 제거 / $T_2$ 의 모든 괄호를 추가하는 비용을 미리 지불했다고 하면, 두 괄호 $A, B$ 를 매치했을 때의 비용은 $C_3 \times \text{(A, B를 매칭하는 데 드는 비용)..