레야몬

1. 문제 함수 f:{1, 2, ..., m} -> {1, 2, ..., m} \(f_{1}(x) = f(x)\) \(f_{n+1}(x) = f(f_{n}(x))\) n, x가 주어질 때 \(f_{n}(x)\)를 계산하는 쿼리를 수행하시오 - 1 - \(m(1 \leq m \leq 200,000)\) - 2 - f(1), f(2), ..., f(m) - 3 - 쿼리의 개수 \(Q(1 \leq Q \leq 20,000)\) - Q개의 줄 - 정수 \(n, x(1 \leq n \leq 500,000, 1 \leq x \leq m)\) 주어지는 n, x마다 \(f_{n}(x)\) 출력 2. 재정의 X 3. 해결 방법 f[i][k] sparse array 4. 실수한 점, 개선할 점 input()을 안으로 뺐다..

1. 문제 N개의 중점으로 된 트리가 있다. 1~N번 매겨져 있고 간선은 1~N-1번 매겨져 있다. 아래 두 쿼리를 수행하는 프로그램을 작성하시오. 1 u v : u->v 경로 비용 출력 2 u v k : u->v 경로 정점 중 k번째 정점 출력 k는 u->v 경로에 포함된 정점 수보다 작다. - 1 - \(N(2 \leq N \leq 100,000)\) - N-1 개줄 - i번 간선 u->v와 비용 \(w(1 \leq w \leq 1,000,000)\) - N+1 - 쿼리의 개수 \(M(1 \leq M \leq 100,000)\) - M개의 줄 - 쿼리 각 쿼리 결과 출력 2. 재정의 X 3. 해결 방법 트리 노드 차수 degree 설정 희소 배열 비용, 노드 메모 비용 : LCA 하면서 더하기 노드 ..

1. 문제 n개의 팀은 1~n번까지 번호가 매겨져 있고 작년과 참가한 팀이 같다. 작년 순위와 상대적인 순위가 바뀐 모든 팀이 주어졌을 때, 올해 순위를 만드시오. 하지만 올해 순위가 결정되지 않을 수도 있고, 잘못된 정보일 수도 있어 이도 알아내야 한다. - 1 - 테스트 케이스의 개수 \(T(1 \leq T \leq 100)\) - 1 - 팀의 수 \(n(2 \leq n \leq 500)\) - 2 - \(t_{i}(1 \leq t_{i} \leq n)\). \(t_{i}\)는 작년에 i 등 한 팀의 번호 - 3 - 상대적인 등수가 바뀐 쌍의 수 \(m(0 \leq m \leq 25,000)\) - m개의 줄 - 상대적인 등수가 바뀐 두 팀. 중복은 X 1등팀부터 순위 출력. 순위가 결정되지 않을 경..

1. 문제 난이도 순서로 된 1~N번까지 총 N개의 문제로 되어 있는 문제를 풀려고 한다. 민오는 세 가지 조건에 따라 문제를 풀 순서를 정한다. N개의 문제를 모두 풀어야 한다. 먼저 푸는 것이 좋은 문제가 있는 문제는, 먼저 푸는 것이 좋은 문제를 반드시 먼저 풀어야 한다. 가능하면 쉬운 문제부터 푼다. 문제의 개수와 먼저 푸는 것이 좋은 문제에 대한 정보가 주어졌을 때, 주어진 조건에 맞는 민오가 풀 문제의 순서를 결정하시오. - 1 - 문제의 수 \(N(1 \leq N \leq 32,000)\), 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 \(M(1 \leq M \leq 100,000)\) - M개의 줄 - 두 정수의 순서쌍 A, B. A번 문제가 B번 문제보다 먼저 푸는 것이 좋다. 항상 문..

1. 문제 전광판의 크기는 전광판에서 한 번에 보이는 최대 문자수를 나타낸다. 광고업자는 길이가 N인 광고를 무한이 붙여서 광고한다. 세준이가 어느 순간 전광판을 쳐다봤을 때, 그때 쓰여 있는 문자가 입력으로 주어졌을 때, 가능한 광고의 길이중 가장 짧은 것을 출력하는 프로그램을 작성하시오. - 1 - 광고판 크기 \(L(1 \leq L \leq 1,000,000)\) - 2 - 현재 광고판에 보이는 문자열 - 1 - 가능한 광고의 길이 중 가장 짧은 것의 길이 2. 재정의 문자열이 주어졌을 때 최소 반복 주기를 구하여라. 3. 해결 방법 KMP failure function을 구한다. L - failure function[last index]가 가능한 광고의 길이중 가장 짧은 것.(정당성 증명은 생략)..

1. 문제 이 모듈은 사건 내에서 가능한 글자가 하나뿐이면 그 글자를 자동으로 입력한다. 모듈이 단어의 첫 글자를 추론하지 않는다. 사전의 모든 단어가 같은 알파벳으로 시작하더라도 반드시 첫 글자는 사용자가 버튼을 눌러 입력하여야 한다. 사건이 주어졌을 때, 이 모듈을 사용하면서 각 단어를 입력하기 위해 버튼을 눌러야 하는 횟수의 평균을 구하시오. 여러 개의 테스트 케이스로 주어져 있다. - 1 - 단어의 개수 \(N(1 \leq N \leq 10^{5})\) - N개의 줄 - 1~80글자인 영어 소문자로만 이루어진 단어. 똑같은 단어가 2번 이상 주어지지 않는다. 각 테스트 케이스마다 주어진 단어의 길이의 총합은 최대 \(10^{6}\)이다. 각 테케마다 문제의 정답을 소수점 둘째 자리까지 반올림하여 ..

1. 문제 N명의 사람과 N개의 일이 있다. 각 사람은 일을 하나 담당해야 하고, 각 일을 담당하는 사람은 한 명이다. 또한 모든 사람은 모든 일을 할 능력이 있다. 사람과 일은 1~N까지 번호가 매겨져 있다. 모든 일을 하는데 필요한 비용의 최솟값을 구하자. - 1 - 사람과 일의 수 \(N(1 \leq N \leq 20)\) - N개의 줄 - 비용 \(D(1 \leq D \leq 10,000)\) 모든 일을 하는데 필요한 비용의 최솟값 2. 재정의 X 3. 해결 방법 비트필드를 이용한 DP 기본 문제 4. 실수한 점, 개선 방법 얘는 비트필드를 이용할 때 DP에서 탐색하는 no와 상관없이 dp가 같기 때문에 통일해도 된다. 이렇게 푼 다른 사람 코드가 있어서 아래에 링크해두었다. #include us..

1. 문제 두 원이 주어졌을 때, 교차하는 영역의 넓이를 소수점 셋째 자리까지 구하시오. - 1 - 두 원의 중심과 반지름 \(x_{1}, y_{1}, r_{1}, x_{2}, y_{2}, r_{2}\) 실수는 최대 소수점 둘째자리까지 구한다 - 1 - 교차하는 영역의 넓이를 반올림해 소수점 셋째 자리까지 출력한다. 2. 재정의 X 3. 해결 방법 두 점 사이의 거리 \(d = \sqrt{(x_{2} - x_{1})^{2} + (y_{2} - y_{1})^{2}}\) 코사인 제2법칙 \(x^{2} + y^{2} - 2xycos(\theta) = z^{2}\) 사인 법칙 \(S = \frac{1}{2} absin(\theta)\) 4. 실수한 점, 개선한 점 X #include #include using ..