문제: AtCoder ARC 135 B — Sum of Three Terms · English · 日本語
길이 N인 배열 A가 주어집니다. 길이 N + 2인 음이 아닌 정수 배열 B가 존재하여 모든 0 <= i < N에 대해
A[i] = B[i] + B[i + 1] + B[i + 2]
를 만족하는지 판정합니다. 존재하면 임의의 배열 하나와 함께 Yes를, 존재하지 않으면 No를 출력합니다.
연속한 두 식을 빼면 다음을 얻습니다.
A[i + 1] - A[i] = B[i + 3] - B[i].
따라서 B의 인덱스를 3으로 나눈 나머지가 같은 원소들은 각각 독립적인 사슬을 이룹니다. 각 사슬의 첫 값을 정하면 이후 값은 A의 차이로 결정됩니다. 나머지가 r인 사슬에서 이 차이들을 누적한 합을 prefix[r]라 하고, 초기값 0도 포함해 그 최솟값을 minPrefix[r]라 합시다. 사슬의 모든 값은 B[r] + prefix[r]이므로, 모든 값을 음이 아니게 하려면 B[r] >= -minPrefix[r]여야 합니다.
나머지 0, 1인 사슬의 시작값은 가능한 최솟값으로 정합니다. 즉 B[0] = -minPrefix[0], B[1] = -minPrefix[1]입니다. 첫 번째 식은 B[0] + B[1] + B[2] = A[0]이므로 B[2] = A[0] - B[0] - B[1]로 결정됩니다. B[2] < -minPrefix[2]이면 해가 없습니다. 세 사슬이 요구하는 최소 시작값의 합이 이미 A[0]보다 크기 때문입니다. 그렇지 않으면 세 사슬의 모든 값이 음이 아니며, 점화식으로 구성한 B는 유효합니다.
N = 1인 경우도 같은 방식으로 처리됩니다. 차이가 없으므로 세 사슬의 최소 누적합은 모두 0이고, A[0]을 음이 아닌 세 값으로 나누면 됩니다. 특히 A[0] = 0이면 구성 결과는 모두 0입니다.
인접한 A 원소를 한 번씩 처리하므로 시간 복잡도는 O(N)입니다. A와 구성한 배열을 저장하므로 공간 복잡도는 O(N)입니다. 차이, 누적합, 구성 값에는 long을 사용합니다.
Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(input.readLine().trim());
long[] a = new long[n];
StringTokenizer tokens = new StringTokenizer(input.readLine());
for (int i = 0; i < n; i++) {
a[i] = Long.parseLong(tokens.nextToken());
}
long[] prefix = new long[3];
long[] minPrefix = new long[3];
for (int i = 0; i + 1 < n; i++) {
int residue = i % 3;
prefix[residue] += a[i + 1] - a[i];
minPrefix[residue] = Math.min(minPrefix[residue], prefix[residue]);
}
long[] b = new long[n + 2];
b[0] = -minPrefix[0];
b[1] = -minPrefix[1];
b[2] = a[0] - b[0] - b[1];
if (b[2] < -minPrefix[2]) {
System.out.println("No");
return;
}
for (int i = 0; i + 3 < n + 2; i++) {
b[i + 3] = b[i] + a[i + 1] - a[i];
}
StringBuilder output = new StringBuilder("Yes\n");
for (int i = 0; i < b.length; i++) {
if (i > 0) {
output.append(' ');
}
output.append(b[i]);
}
System.out.println(output);
}
}