qwerasdfzxcl의 ps 블로그 qwerasdfzxcl의 ps 블로그

2022년부터 IOI 금메달을 받은 학생들을 대상으로 캠프를 진행했는데, 그동안 일정이 되지 않아서 참석하지 못했다. 24년 캠프는 2025년 1월 19일부터 24일까지 홍콩에서 진행됐고, 22-24년 금메달을 초청했다. 대한민국에서는 나랑 이동현, 조영욱 셋이서 참가하게 되었다. IOI 금메달 외에도 EGOI 금메달과 HKOI 금메달을 추가로 초청해서 코치 포함 50명 정도가 참가했다.Day 1 (1/19)아침 9시 비행기를 타고 홍콩으로 갔다. 6시 반에 공항에 도착했는데, 기내에 들고 가도 되는 작은 캐리어를 굳이 수하물로 부치겠다고 줄을 서다가 8시에 겨우 짐을 부치고 8시 50분쯤에 비행기를 탈 수 있었다. 출국장에서 계속 딜레이가 발생해서 새치기할지 백 번 정도 고민하다가 안 했다. 홍콩에 도..

올해 고등학교 3학년을 마치고 내년에 대학교에 입학하게 되었다. 21년부터 23년까지는 거의 모든 시간을 PS에 쏟아부었지만 올해는 PS 말고도 꽤 다양한 일이 있었던 것 같아서 회고록을 간단하게 적어보고자 한다.PS올해는 PS를 많이 하지 않았다. KOI와 선발고사를 응시하지 않았고, NYPC는 나이제한에 걸려서 참가하지 못했다. 작년 IOI가 끝나고 나서부터 PS를 일시적으로 접기로 결심했고 그 이유는 크게 다음과 같다: 1. PS가 좀 재미없어졌다. 예전에는 문제 풀고 코드 짜는 게 되게 재밌었는데, 대회를 잘 쳐야 한다는 압박이 꽤 심해져서 부담이 많이 됐다. 특히 23년 IOI 때 거의 망할 뻔했다가 겨우 살아나서 그 이후로 대회 치는 게 좀 무섭게 느껴졌다.2. 고등학교 3학년이라서 입시에 집..

수학 위주로 좀 풀었다.BOJ 17563 (Mona Lisa)$N(\le 50)$비트 랜덤 정수열 $A$, $B$, $C$, $D$가 주어질 때, $A_i \oplus B_j \oplus C_k \oplus D_l = 0$인 $(i, j, k, l)$을 찾는 문제이다. 각 정수열은 pseduo-random generator와 시드로 표현된다.더보기수열 4개를 동시에 다루는 것은 복잡하기 때문에 먼저 2개씩 묶어서 생각한다. 길이 $2^X$ 정도의 수열 2개를 합치면 상위 $X$비트가 0인 원소 $2^X$개 정도를 얻을 수 있다. 이렇게 하면 상위 $X$비트가 모두 0인 $2^{2X}$개의 페어를 만들 수 있고 이 중 하위 $N-X$비트가 겹치는 페어를 찾으면 된다. 따라서, $X=N/3$정도로 하면 풀 ..

오일러 경로를 구하는 알고리즘은 다음과 같다.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로 끝나는 오일러 경로를 출력하게 된다. 정확히는, 기존에 출력했던 경로 ..

오랜만에 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 가능..

당연한 말이지만 $\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)$에 가능하다..

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 에서 설치할 수 있..

문제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}$에 수렴한다.) 따라서, 페리 수열을 직접 구하는 방..