클래스 8에 속한 문제. sparse table, 혹은 LCA만 알고 있다면 간단한 케이스 분류로 쉽게 풀 수 있다. 한 트리 위의 노드 $a, b, c$를 생각하자. 두 노드 $x, y$에 대해 $x$에서 $y$로 가는 경로를 $P_{xy}$라고 적기로 하고, 이제 $P_{ab}, P_{bc}, P_{ac}$를 생각해 보자. 그럼 다음이 성립한다. 1. $P_{ab}, P_{bc}, P_{ac}$는 항상 유일하게 존재한다. 왜냐? 트리니까. 한 노드에서 다른 노드로 가는 경로가 여러 개 있다는 건 사이클이 있다는 소린데 그럼 트리가 아님. 2. 세 경로 $P_{ab}, P_{bc}, P_{ac}$에 모두 속해 있는 노드는 항상 한 개 이상 존재한다. 트리이기 때문. 만약 그런 노드가 없다면 $a \to..

x축에 타코야끼마냥 중심을 꽂힌 다양한 크기의 구들이 있는데, 이 녀석들의 전체 부피를 구해야 한다. 그런데 서로 겹치는 경우가 생길 수 있기 때문에 그냥 구해서는 안 된다. 뭔가 방법을 써야 한다. 우선 3차원 상황을 그대로 써먹으려고 하면 불편하다. 어차피 문제 상황의 모든 도형이 x축을 중심으로 한 회전체 꼴이기 때문에 2차원 평면 위의 반원들로 차원을 낮추자. 각 공 $S_i = (x - x_i)^2 + y^2 + z^2 \leq r_i^2$들은 이제 $C_i = (x - x_i)^2 + y^2 \leq r_i^2\ (y \geq 0)$으로 생각하자. 그럼 부피는 간단하게 $\displaystyle \pi\int_{a}^{b} y^2dx = \pi\int_{a}^{b} \{r_i^2 - (x - ..

가우시안 수 두 개 주고 GCD를 찾으라는 문제다. 3개의 subtask로 나누어져 있는데, 첫 번째는 새로운 차원을 사용하지 않는 정수 GCD, 두 번째는 아마도 좀 나이브하게 찾는(아니면 arctan 같은 걸 쓴다거나... 우웩.) 방식을 노린 것 같고, 마지막 subtask까지 전부 맞으려면 그보다는 좀 더 머리를 쓰는 방식을 요구하는 것으로 보인다. 우선 이 '가우시안 수' 라는 녀석을 살펴보자. 사실 그냥 복소수다. 이 가우시안 수 간의 곱셈은 다음과 같이 표현됨을 우리는 잘 안다. 두 복소수 $n = a + bi, m = c + di$에 대하여, $n \cdot m = (ac-bd) + (ad + bc)i$. 가우시안 수의 나눗셈에 대해 생각해 보자. 일단 가우시안 수를 서로 나눌 수는 있다...

13334번: 철로 입력은 표준입력을 사용한다. 첫 번째 줄에 사람 수를 나타내는 양의 정수 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 n개의 각 줄에 정수 쌍 (hi, oi)가 주어진다. 여기서 hi와 oi는 −100,000,000이상, 100,000,0 www.acmicpc.net 많은 블로그들에서는 Priority Queue를 사용하는 해설을 적어 놓았고 사실 Priority Queue를 쓰는 게 낫긴 한데, 여기서는 Priority Queue를 안 쓰는 방식을 소개한다. 문제의 철로 L의 오른쪽 끝과 수직선 상에 존재하는 가장 왼쪽의 건물이 처음 만날 때부터 왼쪽 끝이 가장 오른쪽의 건물을 지날 때까지 이동한다고 생각하자. 이 상황을 L이 움직임에 따라 각 건물이 L에 추가되었다가 제거..

2731번: 1379와 세제곱 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 둘째 줄 부터 T개 줄에는 테스트 케이스의 정보가 주어진다. 각 테스트 케이스는 숫자 하나로 이루어져 있고, 이 수는 문제에서 설명한 S이다. S는 www.acmicpc.net 뭔가 허무하게 풀리는 정수론 문제. 우선 문제에서 준 네 수 1, 3, 7, 9를 살펴보자면, $1^3\equiv 1\bmod 10$ $3^3\equiv 7\bmod 10$ $7^3\equiv 3\bmod 10$ $9^3\equiv 9\bmod 10$ 이다. 따라서 $S \bmod 10$의 값으로 찾아야 하는 수 $x$의 첫째 자릿수를 구할 수 있다. ($x_1$) 이제 한 자리씩 $x$의 왼쪽에 붙이면서 수를 찾으면 되는데, 방법은 다음과 같다. ${..

Windows x64 환경에서 동작합니다. .NET 5.0 실행 환경이 필요합니다. 현재 최신 버전은 1.0.0입니다. 2022-02-28: 1.0.0 프로젝트 배포 이전 버전 더보기 아직 이전 버전의 릴리즈 노트가 없습니다. 학생 기록 관리 시스템 (SchoolRecordManagementSystem)은 학교 학생들의 여러 활동을 관리하고 기록하는 데 도움을 주는 소프트웨어입니다. 이하는 소프트웨어 사용 설명입니다. 학생들의 활동을 관리할 수 있는 페이지입니다. [활동 추가] 버튼을 눌러 새로운 활동을 추가할 수 있고, 리스트에서 활동을 선택해 활동의 제목이나 활동 내용을 변경할 수 있습니다. 사진에서 확인할 수 있듯이 중괄호 '{ }' 사이에 0~9 사이의 숫자를 입력하면 이후 학생 정보 관리 페이지..

%2022. 2. 3. 21:40에 작성된 글입니다% 20500번: Ezreal 여눈부터 가네 ㅈㅈ 문제의 답을 $1\,000\,000\,007$로 나눈 나머지를 출력한다. www.acmicpc.net DP 문제 ​ 15의 배수이려면 5의 배수이면서 3의 배수여야 한다. 어떤 자연수 \(N\)에 대하여, \(5\mid N \iff N\mod 10 = 0\ or\ 5\), \(3\mid N \iff 3\mid DigitSum(N)\) 만들어야 하는 수는 1과 5로만 구성되어야 하므로 첫째 자리는 무조건 5다. 이후에는 DP 배열을 만들어서 채워나가는데, \(DP[N][m]\) = 길이가 \(N\)이고 (모든 자리의 수의 합) \(\equiv m\mod 3\)인 수들의 갯수로 두어 1 혹은 5를 더해나가면 ..

%2022. 2. 2 17:36에 작성된 글입니다% 22901번: ko_orange 당신의 출력을 즉각적으로 채점 프로그램에 전달하기 위해, 당신은 모든 출력 뒤에 출력 버퍼를 비워야 한다. 언어별로 출력 버퍼를 비우는 방법은 아래와 같다. C: fflush(stdout); C++: std::cout.flush(); www.acmicpc.net 우선 거짓 응답이 들어오지 않는다고 가정하면 \(\lceil \log_2 300\rceil = 9\)회 탐색을 진행하면 된다. \(q=18\)의 경우 응답이 \(1\)일 때 한번 더 요청을 넣어줘서 확인하면 된다. \(2399\)의 경우에는 전부 \(1\)이니까 \(18\)번 나온다. 그 후에 관찰을 열심히 하면 발견할 수 있는 것들은: 1. 일단 응답 \(0\)..