레야몬

1. 문제 1번부터 n번까지 번호가 붙여진 병사가 있다. 지휘관은 번호가 연속하도록 여러 특공대를 나눈다. 각 병사의 전투력은 \(x_i\)이며 이들로 구성된 특공대의 각 병사 전투력 합이 x라고 할 때 이 특공대의 전투력은 \(ax^2+bx+c\)이다. \((a < 0)\). 각 특공대의 전투력의 합의 최댓값을 구하시오. -1- 전체 병사 수 \(n(1 \leq n \leq 1,000,000)\) -1- 세 정수 a, b, c \((-5 \leq a \leq -1, \left| b \right| \leq 10,000,000, \left| c \right| \leq 30,000,000)\) -1- \(x_1, x_2, ..., x_n (1 \leq x_i \leq 100)\) -1- 각 특공대의 전투력 ..

1. 문제 문자열 S의 서로 다른 부분 문자열의 개수를 구하시오. -1- 문자열 \(S(1 \leq L \ leq 1,000,000)\) -1- 서로 다른 부분 문자열의 개수 2. 재정의 X 3. 해결 방법 ababc의 경우 접미사 배열 ababc, babc, abc, bc, c를 (a, ab, aba, abab, ababc), (b, ba, bab, babc), ...가 부분 문자열이 됨을 알 수 있다. 이 때 겹치는 경우는 접미사 배열에서 lcp에 해당하는 경우이다. 따라서 접미사 배열 전체 글자수 \(N(N+1)/2\)에 LCP만큼 빼주면 서로 다른 부분 문자열의 개수를 구할 수 있다. 접미사 배열은 Manber-Myers Algorithm으로 LCP array를 구한다. 4. 실수한 점, 개선할 ..

1. 문제 상호 접속 네트워크가 주어졌을 때 링 또는 선형 배열로 분리하여 가치의 최댓값을 구하시오. k의 노드로 이루어진 선형 배열은 k-1원, 링은 k원이다. -1- 테스트 케이스 T -1- 노드의 수 \(n(0 \leq n \leq 1,000)\), 단방향 링크의 수 \(m(0 \leq m \leq 30,000)\) -m- 단방향 링크 u, v -T- 분리된 상호 접속 네트워크의 가치의 최댓값 2. 재정의 X 3. 해결 방법 위 문제는 다시 말해 노드가 순방향으로 연결되면서도 최대한 많이 연결되도록 자르는 문제이다. (선형 배열은 k-1개, 링은 k개 연결되어 있다.) 즉, 한 노드에서 다른 노드로 한 번만, 그리고 다른 노드에서 한 노드로 한 번만 연결되므로 이는 이분 매칭으로 최대한으로 연결했을..

1. 문제 랜덤 숫자 생성기(RNG)는 아래와 같은 선형 점화식으로 나타낼 수 있다. \(A_i = (A_{i-1} \times C_1 + A_{i-2} \times C_2 + \cdots + A_{i-k} \times C_k) mod 104857601\) N과 A1, A2, ..., Ak 그리고 C1, C2, ..., Ck가 주어졌을 때, AN을 구하는 프로그램을 작성하시오. 입력 -1- : \(k, N(1 \leq k \leq 30,000, 1 \leq N \leq 10^{18})\) -1- : \(A_i, C_i(0 \leq A_i, C_i < 104857601)\) 출력 -1- A_N 2. 재정의 X 3. 해결 방법 키타마사법에서 다항식의 곱과 나머지 연산을 NTT를 이용해 처리하면 된다. 자세한..

1. 문제 N개의 수로 이루어진 배열 X, Y가 주어진다. 이때 배열은 순환이동이 가능하다. (ex: {1, 2, 3} -> {3, 1, 2}) 점수 S는 아래와 같이 계산한다. \(S=\sum_{i=1}^{N}X[i]\cdot Y[i]\) S의 최댓값을 구하여라. 입력 -1- : 배열의 크기 \(N(1 \leq N \leq 60,000)\) -1- : 배열 X -1- : 배열 Y \((0 \leq x, y < 100)\) 출력 -1-: S의 최댓값 2. 재정의 X 3. 해결 방법 X 배열의 값을 차례대로 계수로 갖는 다항식을 f라고 하자. Y 배열의 값을 역방향으로 계수로 갖는 다항식을 g라고 하자. X와 Y를 곱하면 X 배열의 값과 Y 배열의 곱을 나타내는 항이 N개 만들어지는데 이는 모두 차수가 i..

1. 문제 골프 기계가 할 수 있는 거리 모음 N개의 정수와, 떨어진 구멍까지의 거리 모음 M개의 정수가 주어진다. 두 번 쳐서 공이 들어가는 구멍의 개수는 몇 개인가? 단, 구멍을 향하여 정면으로만 칠 수 있으며 뒤로 치는 것은 불가능하다. 입력 -1- : 정수 \(N(1 \leq N \leq 200,000)\) -N- : 공을 보낼 수 있는 거리 \(k_j(1 \leq k_j \leq 200,000)\) -1- : 정수 \(M(1 \leq M \leq 200,000)\) -M- : 구멍까지의 거리 \(d_j(1 \leq d_j \leq 200,000)\) 출력 -1- : 공이 들어갈 수 있는 구멍의 개수 2. 재정의 N개의 정수중 2개를 중복 가능하게 뽑아서 합이 M개의 정수들 중 같을 수 있는 정수..

1. 문제 N개의 수가 있다. 이 때 다음 쿼리를 수행하라. 1 b c : b번째 수를 c로 바꾸기 2 b c : b부터 c까지의 곱을 구하여 출력하기 - 1 - : 수의 개수 \(N(1 \leq N \leq 1,000,000)\), 수의 변경이 일어나는 횟수 \(M(1 \leq M \leq 10,000)\), 구간의 곱을 구하는 횟수 \(K(1 \leq K \leq 10,000)\) - N개의 줄 - : N개의 숫자 - M+K개의 줄 - : a, b, c; K줄에 걸쳐 구한 구간의 곱을 1,000,000,007로 나눈 나머지를 출력한다. 2. 재정의 유동적인 연속적인 수열의 곱을 계산하라 3. 해결 방법 세그먼트 트리 기본 문제 4. 실수한 점, 개선할 점 no와 start, end를 혼선하지 말기 첫..

1. 문제 반디치는 레스토랑에 가기 전 ATM 기기에 있는 현금 전부를 인출하려고 한다. 반디치는 각 ATM 기기에 현금이 얼마나 들어 있는지 알고 있다. 동일한 도로나 교차로를 여러 번 지날 수 있고, ATM 기기의 현금은 새로 보충되지 않는다. 모든 교차로에는 각각 1개씩 ATM기가 존재하며 레스토랑은 여러 교차로 위에 있고 그중 어느 곳으로 가도 상관없다. 반디치가 출발 장소에서 어떤 레스토랑까지 이동하면서 인출할 수 있는 현금의 최대 액수가 얼마인지를 계산하는 프로그램을 작성하시오. - 1 - 교차로 수, 도로의 수를 나타내는 2개의 정수 \(N, M(1 \leq N, M \leq 500,000)\) 교차로는 1~N까지 번호로 표시된다. - M개의 줄 - 각 도로의 시작 교차로 번호와 끝 교차로 ..