Need not to know

▣ 문제 출처 ─ 제3회 kriiicon ㅅ번 문제 ▣ 알고리즘 분류 ─ 수학 / 구현 / 기하 / 많은 조건 분기 / 미적분학(그린 정리) ▣ solved.ac 기준 난이도 ─ Ruby II 문제 링크: https://www.acmicpc.net/problem/11392 약 한 달 전쯤, 모 세미나(?)에서 본 문제의 풀이에 대해 발표할 일이 있었어서 발표 자료를 만들었는데… 나름대로 열심히 만든 자료를 한 번 발표하는 데 쓰고 끝내기는 좀 아까워서 여기에도 올려봅니다! (파일 저장 후 '읽기 전용'으로 여시면 됩니다.) 원본 발표 자료에서 개인 정보나 문제 풀이와 관련 없는 부분 등을 조금 수정한 버전입니다. 이 문제를 도전하시는 분들에게 조금이라도 도움이 되셨으면 좋겠습니다. :) 덧붙여, 본 문제..

▣ 문제 출처 ─ 제1 회 곰곰컵 G번 문제 ▣ 알고리즘 분류 ─ 수학 / 확률론(기댓값의 선형성) / 조합론(더블 카운팅) ▣ solved.ac 기준 난이도 ─ Gold II (개인적으로는 골1 정도라고 생각한다.) 문제 링크: https://www.acmicpc.net/problem/25197 $N$명의 사람들이 서로 다른 $K$개의 조에 균등한 확률로 랜덤하게 나뉘어 들어간다. 각 조에서 모든 쌍이 식사를 한 번씩 한다고 할 때, 전체 식사 횟수의 기댓값은 얼마일까? 일단 $N$명의 사람들이 $K$개의 조에 들어가는 모든 경우의 수는 $K^N$가지인 걸 알고 있으므로 총 식사 횟수의 합을 구할 수 있으면 되는데, 모든 경우에 대해 일일이 식사 횟수를 구하는 건 범위상 당연히 불가능하다. 그런데 어차..

모두 Happy New Year! ▣ 정수론 시리즈 ─ 순서대로 읽으시는 걸 추천합니다. 1. 뫼비우스 함수와 디리클레 합성곱 2. Double Counting과 Harmonic Lemma 3. 곱셈적 함수 테이블 만들기 4. Mertens Trick (xudyh's sieve) (현재 글) Intro 이번에도 문제 하나를 소개하면서 시작한다. Problem. 오일러 토션트 함수의 합 양의 정수 $N$이 주어질 때, 다음 식의 값을 1초 안에 구하는 프로그램을 작성하시오. (단, $N \le 10^9$이다.) $$S_{\phi}(N) = \sum_{n=1}^N \phi(n)$$ 이전 글에서 소개했듯이, 오일러 토션트 함수의 테이블을 $\mathcal O(N \log N)$에 채울 수 있으므로 $\phi(..

모두 메리 크리스마스! ▣ 정수론 시리즈 ─ 순서대로 읽으시는 걸 추천합니다. 1. 뫼비우스 함수와 디리클레 합성곱 2. Double Counting과 Harmonic Lemma 3. 곱셈적 함수 테이블 만들기 (현재 글) 4. Mertens Trick (xudyh's sieve) 「뫼비우스 함수와 디리클레 합성곱」 게시글에서 여러 곱셈적 함수들의 예시를 소개하였다. 본 글에서는, 곱셈적 함수들의 테이블을 만드는 코드들을 작성해 볼 것이다. 여기서 "함수의 테이블을 만든다"의 의미는 어떤 양의 정수 $N$과 함수 $f(n)$에 대해 $f(1)$, $f(2)$, $\cdots$, $f(N)$의 값을 모두 구한다는 의미이다. 양의 약수의 개수 $\tau(n)$ naive하게 $N$개의 값을 모두 구하면 $\..

▣ 문제 출처 ─ Polish Olympiad in Informatics(POI) 2005/2006 Stage 1의 5번 문제 ▣ 알고리즘 분류 ─ DFS / 이분 탐색 / 스위핑 / 기하 / CHT(Convex Hull Trick) ▣ solved.ac 기준 난이도 ─ Diamond IV (개인적으로는 다3 정도라고 생각한다.) 문제 링크: https://www.acmicpc.net/problem/1909 크기 $S = W_x \times W_y$ 그리드에 $n$개의 '특별한 점'이 주어진다. $(sx,\, sy)$에서 $(tx,\, ty)$로 가는 임의의 경로에 대해, 경로상의 임의의 점과 특별한 점들 사이 거리의 최솟값을 최대화하는 문제다. 일단 최솟값을 최대화하는 건 나중에 생각하기로 하고, 문제..

인접행렬과 인접리스트 $V$개의 정점이 있고 $E$개의 간선(방향이든 무방향이든 상관없지만, 여기서는 편의를 위해 무방향이라 가정하자)이 있는 그래프 $G(V,\, E)$를 생각하자. 이러한 그래프를 저장하는 방법은 크게 두 가지가 있다. 첫 번째는 인접행렬(Adjacency Matrix)이다. 어떤 두 점이 인접한지, 즉 두 점 사이에 간선이 있는지를 표시하는 행렬로 그래프를 표현한다. 실제 프로그래밍에서는 아래 코드와 같이 $V \times V$ 크기의 배열 g를 사용해서 g[A][B] 값을 A번 정점과 B번 정점 사이 간선의 개수로 저장한다. #include #define NMAX 1000 int g[NMAX][NMAX]; int main() { int N, M; scanf("%d%d", &N, &..

▣ 문제 출처 ─ 2019년도 서울대학교 프로그래밍 경시대회(SNUPC) Div. 1 G번 문제 ▣ 알고리즘 분류 ─ 수학(미적분학, 기하학, 확률론) ▣ solved.ac 기준 난이도 ─ Diamond II 문제의 내용은 여기에서 볼 수 있다. 필요하지 않은 스토리텔링 부분을 제외하면 문제의 내용은 한 줄로 요약할 수 있다: 다각형이 주어질 때, 다각형 내의 임의의 두 점 사이 거리의 제곱의 기댓값을 구하는 것이 목표다. 다각형 내의 점은 연속적으로 분포하므로 적분을 써야한다는 것을 쉽게 짐작할 수 있다. 주어지는 다각형의 전체 넓이(혹은 다각형 그 자체)를 $S$라고 하자. 두 점의 좌표를 각각 $(x_1,\, y_1),\, (x_2,\, y_2)$라 하면 거리의 제곱은 $(x_1 - x_2)^2 +..