레야몬

1. 문제 도현이는 경기장을 여러 구역으로 나누고, 어떤 선수가 A->B 움직임을 (A, B)로 표현한다. 다른 모든 구역에 도달할 수 있는 시작구역을 모두 찾자. - 1 - 테스트 케이스의 개수 \(T(1 \leq T \leq 11)\) - 1 - 구역의 수 N, 지시한 움직임의 수 M \(1 \leq N, M \leq 100,000)\) - M개의 줄 - 움직임 (A, B) \(0 \leq A, B < N)\) 가능한 모든 시작 구역을 오름차순으로 출력, 만일 그러한 시작 구역이 없으면 Confused 출력 2. 재정의 시작하면 모두 연결되는 정점 모두 출력 3. 해결 방법 SCC 알고리즘으로 구역 나누기 연결되는 그룹들을 모두 제거했을 때 남은 그룹의 개수가 1개면 그 그룹의 모든 원소. 0개면 모..

1. 문제 한 도미노 블록이 넘어지면 다음 도미노가 연쇄적으로 쓰러진다. 그러나 특정 다른 블록을 넘어뜨리지 못하게 배치되어 있다면 수동으로 넘어뜨려야 한다. 각 도미노 블록 배치가 주어질 때, 모든 블록을 넘어뜨리기 위해 손으로 넘어뜨려야 하는 블록 개수의 최솟값을 구하라. - 1 - 테스트케이스의 개수 T - 1 - 정수 \(N, M(1 \leq N \leq 100,000)\) N: 도미노 개수, M: 관계의 개수 도미노 블록 번호는 1~N사이 정수다. - M개의 줄 - 두 정수 x, y(x번 블록이 넘어지면 y번 블록도 넘어짐) 손으로 넘어뜨리는 최소의 도미노 블록 개수 출력 2. 재정의 모든 노드를 다 지나기 위해 시작해야 되는 최소 노드 수 3. 해결 방법 SCC로 그룹 짓기 if(scc[i] ..

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}\)이다. 각 테케마다 문제의 정답을 소수점 둘째 자리까지 반올림하여 ..