구사과

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)$ 에 전처..

가중치 있는 방향 그래프 $G$ 에서 두 정점 $s, t$ 가 쿼리로 주어질 때, $s$ 에서 $t$ 로 가는 최단 경로를 구하는 문제를 흔히 모든 쌍 최단 경로 문제 (All-Pair Shortest Path, APSP) 문제라고 부른다. APSP 문제는 그래프 이론의 기초적인 문제 중 하나로, Floyd-Warshall Algorithm을 사용하여 $O(n^3)$ 시간에 해결하는 방법이 아주 잘 알려져 있으며 알고리즘을 공부하다 보면 누구나 접하게 될 기초 알고리즘 중 하나이다. Floyd Warshall Algorithm은 APSP 문제에 대해서 다음과 같은 자료구조를 만드는 알고리즘이라고 볼 수 있다: 자료 구조의 초기화에는 $O(n^3)$ 이 걸린다. 자료 구조는 $O(n^2)$ 의 메모리를 사..