스코어보드는 여기서 볼 수 있다. 5, 6위팀과 페널티 4분이라는 근소한 차이로 전체 4등 / 90팀으로 대회를 마무리했다. 예선 본선 모두 4등이다. 팀원은 imeimi, TAMREF, jhhope1. A Bus With No Drivers 팀처럼 컴공과가 한 명밖에 없는 팀이다 ㅋㅋ 팀 전략, 사전 연습, 팀노트 즈홒(jhhope1)은 풀이를 내는 능력이 뛰어난 데 비해 아직 구현이 익숙하지 않았고, 나는 코딩이 빠른 편이지만 풀이를 잘 못 만들었다. imeimi는 단점이 없다. 그냥 이멘이다 ㅋㅋㅋ 그래서 즈홒은 코딩을 잡지 않았고, 내가 Soulless Coding Machine 역할을 하면서 즈홒과 이멘이 주는 풀이를 구현하는 위주의 전략을 사용했다. 레드코더 2 ~ 2.5명 정도가 팀에서 낼 ..

고등학생 때 확률과 통계에서, 빠르면 중학생 때 수학올림피아드에서 접하게 되는 Stirling number \(S(n,k)\)에는 항상 제 2종 이라는 수식어가 붙는다. 교과서에서 보이지도 않는 제 1종 스털링 수가 뭐기에 더 쓸모가 많은 \(S(n,k)\)를 "제 2종"이라고 이름붙인 걸까? Notations & Preliminaries - \([n]\)은 양의 정수 집합 \(\{1,2,\cdots,n\}\)을 의미한다. - Falling factorial \(\displaystyle (x)_{k} := x(x-1)\cdots(x-k+1) = k! \cdot \begin{pmatrix}x\\k\end{pmatrix}\). - 제 2종 스털링 수의 조합적 의미를 깊게 다루지는 않는다. - 서술을 엄밀하게..

Pentagonal Number Theorem은 분할수 \(p(n)\)을 \(\mathcal{O}(n^{1.5})\)에 구할 수 있게 해주는 멋진 점화식이다. BOJ 문제는 모르고, Project Euler 78번 으로 연습해볼 수 있다. koosaga님이 추천해주신 꿀이 뚝뚝 떨어지는 왕기초 연습문제도 Codeforces에 있다. 생성함수에 대한 기본적인 지식을 전제한다. 이탤릭체로 표기된 용어는 임의로 지어낸 용어로, 공식적인 용어와 다를 수 있다. 분할수와 그 생성함수 자연수 \(n \ge 0\)의 분할수 \(p(n)\)이란, 합이 \(n\)이 되는 단조 감소하는 자연수열(분할)의 개수를 말한다. 물론 빈 수열의 합은 0이기 때문에 \(p(0) = 1\)이다. 엌ㅋㅋㅋㅋㅋ 좀 더 정상적인 예시로, ..

이 포스팅에서 다룰 것은 AKS primality test에 사용하는 lemma 중 하나로, \(n \ge 7\)에 대해 \(\ell_{n} := \mathrm{lcm}(1,2, ... , n) \ge 2^{n}\)이 성립한다는 것이다. 사실 Prime Number Theorem에 의해서 \(\ell_{n} \sim e^{n}\)이 성립하기 때문에, 충분히 큰 \(n\)에 대해서는 자명히 성립하는 부등식이다. 다만 PNT가 좀 overkill이기도 하고, 기왕 non-analytical한 증명이 있으니 이야기해보도록 하자. 증명은 다음의 글에서 가져왔다. https://math.stackexchange.com/questions/851328/textlcm1-2-3-ldots-n-geq-2n-for-n-ge..

문제 링크 10076번: 휴가 문제 지안지아는 타이완에서의 휴가를 계획하고 있다. 휴가동안 지안지아는 도시에서 도시로 이동하고 도시 안의 관광지들을 방문할 것이다. 타이완에는 하나의 고속도로를 따라서 개의 도시들이 위치한다. 이 도시들은 순서대로 0부터 n-1까지의 번호가 붙어있다. 임의의 i(0 < i < n-1)에 대해서, 도시 i의 인접한 도시는 도시 i-1과 i+1이다. 도시 0과 인접한 도시는 도시 1뿐이고, 도시 n-1과 인접한 도시는 도시 n-2뿐이다. 각 도시에는 여러 www.acmicpc.net PS-hell 스터디에서 가장 먼저 해결한 문제다. 문제 내용 길이 \(n\)의 선형 배열 \(a[0\ldots n-1]\)가 있다. \(s\)번째 entry에서 시작해서 한 턴에 다음의 동작들을..

문제 링크 14859번: 세 쌍 서로소 크기가 n인 수열 a1, a2, ..., an이 주어졌을 때, 1 ≤ i < j < k ≤ n 이면서, GCD(ai, aj, ak) = 1인 세 쌍 (i, j, k)의 개수를 구하는 프로그램을 작성하시오. 여기서 GCD는 최대공약수를 의미한다. www.acmicpc.net \(\text{MAX} = 10^6\) 범위의 수가 \(n\) 개 주어져 있고, 이 중에서 \(\gcd\)가 1인 triplet의 개수를 구하는 문제이다. 썸네일 스포 방지를 위한 텍스트입니다. 썸네일 스포 방지를 위한 텍스트입니다. 썸네일 스포 방지를 위한 텍스트입니다. 썸네일 스포 방지를 위한 텍스트입니다. 썸네일 스포 방지를 위한 텍스트입니다. 썸네일 스포 방지를 위한 텍스트입니다. 썸네일 ..