레야몬

1. 문제 한 심사위원은 반드시 찬성 또는 반대하는 두 사람을 고른다. 심사위원은 자신이 행사한 두 표 모두 반대되는 결과가 나오면 의심한다. 상근이가 포함된 다음 라운드 진출목록을 만들 수 있는지 없는지 구하시오. - 1 - 참가자의 수 n, 심사위원의 수 m \(2 \leq n < 1,000, 1 \leq m < 2,000)\) - m개의 줄 - 각 심사위원이 행사한 루트의, 정보 a, b \((1 \leq \left| a \right| , \left| b \right| \leq n, \left| a \right| \neq \left| b \right|)\) 정보가 x0인 경우 찬성표를 던질 것이다. 참가자의 번호는 1~n번이다. 상근이는 1번 참가자이다. 다음 라운드 진출 목록을 심사위원의 의심 없..

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]가 가능한 광고의 길이중 가장 짧은 것.(정당성 증명은 생략)..