전체 글
-
오일러 경로?알고리즘 2024. 8. 27. 22:09
오일러 경로를 구하는 알고리즘은 다음과 같다.void dfs(int now){ for(int nxt=1; nxt 0){ g[now][nxt]--; g[nxt][now]--; dfs(nxt); } } printf("%d ", now);} 나는 이 코드와 알고리즘에 대한 설명을 읽고 이해를 할 수 없었다. "dfs하면서 사이클을 찾으면 끼워 넣는다"로 보통 설명하는 것 같은데, 어떤 사고를 거치면 저런 코드가 나오는 것일까? 이에 대해 오랜 시간 고민해봤지만 아직도 잘 모르겠다. 그래도 다행인 점은 적어도 내가 납득할 수 있는 설명을 찾았다는 것이다. dfs(now)를 호출하면 현재 그래프에 남아있는 간선을 사용해서 now로 끝나는 오일러 경로를 출력하게 된다. 정확히는, 기존에 출력했던 경로 ..
-
PS 일지 (4/19 ~ 5/5)카테고리 없음 2024. 5. 4. 21:15
오랜만에 AGC + 랭작을 했다. AGC066A. 체스보드 컬러링 후 mod 2d 기준 0/d로 맞추면 된다.B. 못 풀겠어서 풀이를 봤다. 5^i는 2를 곱할 때마다 자릿수 합이 감소하는 경향을 보인다. 적당히 5의 거듭제곱을 많이 이어 붙여서 노이즈를 제거하자.C. 못 풀겠어서 풀이를 봤다. 제거 가능할 필요충분조건은 A가 B의 2배면서 왼쪽이나 오른쪽 끝에 B가 있는 경우다. 이를 이용하면 dp를 할 수 있다.D. 몇 개의 점은 고정하고 그 주변에 있는 A를 퍼뜨린다는 느낌으로 해를 표현할 수 있다. 각 점을 고정했을 때 영향을 받는 구간을 모두 구한 후 dp를 돌리면 된다.E. BOJ 18873이랑 같다. 돌의 배치를 고정해두고 swap 가능한 두 점을 모두 찾아보자. 부모가 자식과 swap 가능..
-
1^k + 2^k + ... + n^k를 O(k)에 구하기알고리즘 2024. 3. 26. 16:44
당연한 말이지만 $\mathbb{Z}_p$에서 생각한다. Lagrange interpolation 구하려는 식은 $n$에 대한 $k+1$차 다항식이라는 사실이 알려져 있다. 따라서, $k+2$개의 함숫값만 알고 있으면 Lagrange interpolation을 통해 값을 계산할 수 있다. 함숫값을 구하는 건 거듭제곱을 해야 하기 때문에 $O(k \log k)$의 시간이 걸리고, $f(n)$을 계산하는 것은 역원을 나이브하게 계산할 경우 $O(k \log p)$의 시간이 걸린다. 사실 이 정도면 충분히 빠르다. TLE가 난다면 쓰레기 문제라는 뜻이기 때문에 풀지 않는 것을 권장한다. Linear sieve 사실 $i^k$를 $i=0, 1, \ldots, k+1$에 대해 계산하는 것은 $O(k)$에 가능하다..
-
AlphaGeometry 체험 후기일기장 2024. 1. 21. 11:55
https://deepmind.google/discover/blog/alphageometry-an-olympiad-level-ai-system-for-geometry/ AlphaGeometry: An Olympiad-level AI system for geometry Our AI system surpasses the state-of-the-art approach for geometry problems, advancing AI reasoning in mathematics deepmind.google 최근 구글 딥마인드에서 mo 기하 문제를 푸는 AI를 발표했다길래 궁금해져서 직접 설치하고 실행해봤다. https://github.com/google-deepmind/alphageometry 에서 설치할 수 있..
-
N번째 페리 수열의 K번째 항을 빠르게 구하기알고리즘 2023. 11. 26. 23:46
문제0 이상 1 이하인 분모가 $N$이하의 기약분수를 크기 순으로 나열한 수열을 $N$번째 페리 수열 (Farey Sequence)라고 한다. $N$과 $K$가 주어졌을 때, $N$번째 페리 수열의 $K$번째 원소를 구하여라. BOJ 1882와 동일한 문제고, 올해 ICPC 예선에도 출제된 문제이다. 이 글에서는 $N$이 고정이고 $K$가 쿼리로 주어질 때 전처리 $O(N^{\frac{2}{3}})$, 쿼리 $O(\sqrt{N} \log^{1.5}{N})$ 시간에 이 문제를 해결하는 방법에 대해 다룬다. 문제 변형하기$n$번째 페리 수열의 길이는 $\Theta(n^2)$임이 널리 알려져있다. (서로소인 쌍의 개수의 비율이 $\frac{6}{\pi^2}$에 수렴한다.) 따라서, 페리 수열을 직접 구하는 방..
-
IOI 2023 후기일기장 2023. 9. 11. 15:41
8/28 ~ 9/4에 헝가리에서 열린 IOI 2023에 한국 국가대표로 참가했다. 한국 팀 멤버는 박상훈(qwerasdfzxcl), 반딧불(79brue), 이동현(lisifu/kizen), 이성호(puppy/windva)였고, 작년에 비해 꽤 강한 멤버였기 때문에 4금을 노려볼만하다고 생각했다. 나와 동현이는 금메달을 받았고, 딧불이와 성호는 은메달을 받으면서 2금2은의 성적을 기록했고, 국가 순위 5등을 했다. 작년에도 IOI에 참가했지만 코로나 이슈로 온라인으로 참가하게 되어서 대회만 치고 끝났는데, 올해는 오프라인으로 직접 헝가리도 가고 여러 행사나 관광을 즐길 수 있어서 매우 좋았다. 솔직히 말하자면 관광은 별 거 없어서 재미없었고 공통 관심사를 가진 외국인 친구들을 많이 만날 수 있었던 것이 너..
-
imos-Hanbyeol Trick and its applications알고리즘 2023. 6. 11. 15:55
(2023.06.11 online IHT with linear memory 문단 추가) 이 글에서는 imos법을 확장한 imos-Hanbyeol Trick (IHT)의 개념과 응용에 대해 설명한다. imos법 imos법이란 구간 덧셈 업데이트를 빠르게 처리하는 테크닉이다. 다음과 같은 문제를 생각해보자. 0으로 초기화된 $N \times N$ 크기의 $2$차원 배열 $A$가 주어진다. 다음 연산을 $Q$개 처리한 후 배열을 출력하여라. $x_1$ $y_1$ $x_2$ $y_2$ $z$: $A[x_1:x_2][y_1:y_2]$에 $z$를 더한다. (앞으로 모든 : notation은 닫힌 구간이다.) 나이브하게 했을 때 시간복잡도는 최악의 경우 $O(QN^2)$이지만, imos법을 사용하면 $O(Q+N^2)..
-
2023 IOI 멘토교육 5주차일기장 2023. 5. 29. 17:17
CEOI 2016을 돌았다. 0:00 ~ 1:47 1번과 2번을 읽었다. 1번은 나이브가 쉽고 풀태는 바로 안 떠올라서 2번을 읽고 풀었다. 나이브랑 풀태 모두 자꾸 틀려서 시간을 많이 날렸다. 처음에 dnc opt 풀이랑 덱dp 풀이를 내서 둘다 짰는데 둘다 틀린 풀이였다. 100점 받으려면 대충 비트스트링 들고 다니면서 적당히 dp 돌려주면 O(NTS)에 문제를 해결할 수 있다. 1:47 ~ 3:34 3번을 읽었다. input 노드 루트개 / output 노드 루트개 연결하는 노드들을 만들고 연결하면 47점을 받을 수 있다. 100점을 받으려면 이를 다중으로 해주면 된다. i번째 층의 노드는 input 노드 P^(i/k)개, output 노드 P^((k-i)/k)개를 연결하는 노드라고 놓으면 추가 노..