구사과

82등으로 본선 진출 실패했습니다. ucpc 예선 1등해서 기분 좋았는데 느슨했던 멘탈에 긴장감을.. 5번 이러면 될 거 같은데..? 옛날에 민컷 이야기라는 글도 썼고 나름 컷 문제는 잘 푼다고 생각했는데 아닌가.. 디닉도 팀노트 없이 짤 수 있는데... i -> j 로 가는 간선이 있으면 source -> i로 가중치 b의 유향 간선 잇고 i -> sink로 가중치 a의 유향 간선 잇고 i -> j로 가중치 c - a의 유향 간선 잇고 j -> i로 가중치 c - b의 유향 간선 잇고 그러면 (i, j) 가 모두 source쪽에 있으면 (주거) a의 비용 (i, j) 가 모두 sink쪽에 있으면 (업무) b의 비용 i가 source, j가 sink쪽에 있으면 (c-a) + a = c의 비용 i가 sin..

(6/23 01:20: 7월 과외 마감하였습니다. 많은 성원에 진심으로 감사드립니다.) 안녕하세요. 구재현입니다. 학교 복학을 위해서 최근에 회사를 그만 두었는데, 2달 정도 여유 시간이 있어서 그동안 알고리즘 과외를 진행해 볼까 합니다. 프로필 글 작성 시간 기준으로 변동이 있을 수 있습니다. BOJ: koosaga (Rank 1, 11310 solved) solved.ac: koosaga (Rank 1, Master, 3255) Codeforces: ko_osaga (World Rank 13. Korea Rank 1, Legendary Grandmaster, 3315) Google Code Jam World Finals 2회 출전 (2021, 2020) Facebook Hacker Cup World ..

https://epubs.siam.org/doi/epdf/10.1137/1.9781611973099.139 Andreas Bjorklund는 그래프 이론에 대수적 방법을 접목시켜서 50년짜리 SOTA를 여럿 깬 것으로 유명하다. 최근에 논문 중 하나를 읽어볼 기회가 생겼는데 생각보다 훨씬 elementary한 방법이라서 놀랐다. 간단하게 요약하면 좋을 것 같아서 짧은 노트를 써 본다. 문제는 "그래프가 있고 K개의 정점이 마크되어 있을 때 이 정점들을 모두 지나는 최소 길이 simple cycle을 찾는 문제" 이고, 시간 복잡도 aim은 $O(2^k poly(N))$ 이다. 풀이는 다음과 같다. 먼저 찾을 사이클의 시작점을 $k$ 개 중 하나로 고정하자. 다음과 같은 walk $w = \{s, v_1,..