전체 글
-
2026 ICPC Asia Seoul Regional 후기일기장 2026. 11. 17. 00:32
서론지난 글(https://qwerasdfzxcl.tistory.com/62)에 대충 다 적혀있다. 우리 팀의 목표는 서울 리저널 우승이었고, 멤버 전부 어느 정도 기본 실력이 있기 때문에 팀연습만 적당히 하는 식으로 대회를 준비했다. 올해 진행한 팀연습 결과는 다음과 같다. 2026 ICPC Asia Pacific Championship(260405, 10솔 1453분): 유찬이가 마지막에 G 풀이를 찾아서 10솔브를 했다.2025 Asia Yokohama Regional Contest(260721, 9솔 1071분): BFK를 못 풀었는데 별로 쉽지 않은 문제인 것 같다.2026 ICPC Latin America Championship(260905, 10솔 1950분): 페널티가 너무 많았고 남은 문..
-
The 4th Universal Cup Semifinals 후기일기장 2026. 11. 16. 13:16
https://youtu.be/-N3LRKUuiu0서론PS를 거의 접은 상태로 1년 넘게 지낸 것 같다. 주요 대회에는 대부분 참가하지만 개인적으로 시간을 내서 문제를 풀지는 않는다. 오래전부터 PS를 완전히 접고 다른 걸 하고 싶다는 생각이 있었는데, 완전히 접었을 때 보는 손해가 너무 크고, 마땅히 할 것도 없어서 접지 못하고 있다. 4th Ucup Semifinals는 ICPC 팀연습도 할 겸 floor_sum 2기(나, 이지후(numbering), 이유찬(lighton))으로 참가했다. 원래 후기도 귀찮아서 안 적는데, finals 진출권에 드는 성적이기도 하고 녹화 영상이 아까운 것 같아서 좀 적어보기로 했다. 내가 어떤 방식으로 구현했는지 관심이 있다면 영상이랑 같이 보면 된다. 시작 전30분..
-
a_1, a_2, ..., a_n이 주어졌을 때 a_1^{-1}, a_2^{-1}, ..., a_n^{-1}을 O(n + log mod)에 구하기알고리즘 2026. 9. 24. 12:18
팩토리얼 역원 전처리랑 똑같은 아이디어다. $b = [1, a_1, a_1a_2, \cdots, a_1a_2\cdots a_n]$을 계산하자. 이는 $O(n)$이 걸린다. $c = [1, a_1^{-1}, (a_1a_2)^{-1}, \cdots, (a_1a_2\cdots a_n)^{-1}]$이라고 하면, $c[n] = b[n]^{-1}$이고, $c[i] = c[i+1] \times a_{i+1}$이므로 $c$를 $O(n+\log mod)$에 계산할 수 있다. $a_i^{-1} = b[i-1] \times c[i]$이므로 문제가 해결됐다.
-
f(k)=0^k + 1^k + ... + (n-1)^k일 때 f(0), f(1), ..., f(m-1)을 O(mlogm)에 구하기알고리즘 2026. 9. 24. 12:08
https://qwerasdfzxcl.tistory.com/39 예전에 이런걸 쓴적이 있는데, 그 이후로 이걸 요구하는 문제를 본 적이 없다... 이번 글은 실제로 꽤 많이 쓰이는 알고리즘이다. (백준 1386 f와 g, 2025 마닐라 리저널 K, ARC++ 230 D) 풀이$0^0=1$로 가정한다. EGF로 생각하면 매우 쉽다.$$\begin{align*} g(x) &= \sum_{k=0}^\infty \frac{f(k)}{k!} x^k \\ &= \sum_{k=0}^{\infty} \sum_{i=0}^{n-1} \frac{i^k}{k!}x^k \\ &= \sum_{i=0}^{n-1} \sum_{k=0}^\infty \frac{i^k}{k!}x^k \\ &= \sum_{i=0}^{n-1} e^{ix}..
-
-
Power Projection of Set Power Series알고리즘 2026. 4. 25. 13:10
이 글과 동일한 내용이다.Introduction이 글에서는 power projection of set power series를 $O(N^2 2^N+M)$에 계산하는 알고리즘에 대해 알아볼 것이다. 이를 이용해 정점이 $N$개인 그래프의 chromatic polynomial을 $O(N^2 2^N)$에 계산하는 알고리즘도 함께 다룬다. 이 글에서는 Operations on Set Power Series의 내용을 모두 이해했다고 가정하고 설명한다.Power Projection of Set Power SeriesSet $G = \{ g_0, g_1, \cdots, g_{N-1} \}$과 commutative ring $R$에 대해 정의된 set power series $\mathcal S_G(R)$에 대해 생각..
-
-