Codeforces Round #750 (Div. 2)-D. Vupsen, Pupsen and 0

문제 설명

카파와 수아는 정수 배열을 선물받았다. 카파는 숫자 $0$을 싫어하기 때문에 카파는 배열에서 $0$을 다 버려버렸다. 그 결과 길아기 $n$인 배열 $a$를 얻었다.

수아는 반대로 숫자 $0$을 좋아하기 때문에 $0$을 제외한 숫자로만 이루어져 있는 배열을 보고 화가 났다. 수아를 응원하기 위해서 카파는 길아가 $n$인 또 다른 배열 $b$를 생각해 냈다. 이 배열은 $\sum_{i=1}^{n} a_i \cdot b_i = 0$ 을 만족한다. 카파는 숫자 $0$을 싫어하기 때문에 배열 $b$는 숫자 $0$이 포함하면 안된다. 또한 숫자는 반드시 크면 안된다. 따라서 배열 $b$ 원소의 절대값의 총합이 $10^9$를 넘어가면 안된다. 위의 조건을 만족하는 배열 $b$를 찾을 수 있도록 도와주자.

Input
첫번째 줄에는 테스트 케이스의 개수를 나타내는 정수 $t (1 \le t \le 100)$ 이 주어진다.

각 테스트케이스의 첫번째 줄에는 배열의 길이 $n (2 \le n \le 10^5)$ 가 주어진다.

각 테스트케이스의 두번째 줄에는 배열 $a$의 원소인 n개 정수 $a_1, a_2, ..., a_n (-10^4 \le a_i \le 10^4, a_i \neq 0)$ 가 주어진다.

Output
각 테스트 케이스마다 원소 $n$개 $b_1, b_2, ..., b_n (|b_1| + |b_2| + ... + |b_n| \le 10^9, b_i \neq 0, \sum_{i=1}^{n} a_i \cdot b_i = 0)$ 로 이루어진 배열 $b$를 출력한다.

Example
input
3
2
5 5
5
5 -2 10 -9 4
7
1 2 3 4 5 6 7

output
1 -1
-1 5 1 -1 -1
-10 2 2 -3 5 -1 -1

문제 접근

사용한 알고리즘: 수학, 구성적
걸린 시간 : 00:10
C번에서 너무 시간을 끌어서 이 문제를 깊이있게 생각 할 수 가 없었던 것 같다. C번을 버리고 바로 이 문제를 1시간 반동안 생각했으면 풀었을 수도 있을 것 같다. 이 문제는 구성적 알고리즘을 사용하는 전형적인 문제인 것 같고 몇가지 테스트 케이스를 직접 만들어서 생각해보면 규칙성이 보인다.

먼저 배열의 길이가 짝수인 경우 쉽게 풀 수 있다. 만약 배열 $a$가 $[1, 2, 3, 4]$ 로 이루어져 있다고 하면 배열 $b$는 다음과 같이 만들 수 있다. 각 배열을 2개씩 묶은 수를 $(a, b)$ 라고 하면 $(b, -a)$이런 식으로 배열을 구성하면 배열의 길이가 짝수 인경우 무조건 $b$를 구할 수 있다. 따라서 $b$는 $[2, -1, 4, -3]$ 으로 만들면 된다.

그렇다면 배열의 길이가 홀수인 경우 어떻게 풀까? 일단 배열에서 맨 앞에 있는 원소 3개를 빼면 뒤에 남아있는 배열은 짝수 길이 배열이기 때문에 위에서 언급한 배열의 길이가 짝수인 경우 배열을 구성하는 방법을 통해서 쉽게 구할 수 있다. 그러면 남아있는 숫자 3개로 어떻게 0을 만들 수 있을까? 배열 $a$의 원소를 $a_1, a_2, a_3$이라고 하고, 배열 $b$의 원소를 $x, y, z$라고 하자. 그러면 우리가 풀어야 할 식은 $a_1x + a_2y + a_3z = 0$ 이다. 살짝 생각하기 어려울 수 있는데, $x = -a_3, y = -a_3, z = (a_1 + a_2)$라고 하면 해를 구했다. 그런데 여기서 $z$가 살짝 문제다. 배열의 원소는 $0$이 되면 안되는데, $a_2 = -a_1$이면 $z$가 $0$이 되기 때문에 답이 아니다. 그렇기 때문에 $z = (a_1 + a_2)$인 경우, $y = (a_1 + a_3)$ 인경우 $x = (a_2 + a_3)$ 인경우 모두를 고려해서 답을 구하면 된다.

맨 마지막에 있는 조건은 무조건 맞출 수 있을까? 일단 모든 원소가 $10^4$로 이루어져 있는 배열의 길이가 $10^5$인 경우를 생각해보자. 배열의 길이가 짝수이기 때문에 총 배열의 합은 $10^4 \cdot 10^5 = 10^9$ 이기 때문에 조건을 만족한다.

배열의 길이가 $10^5 - 1$인 경우는 어떨까? 일단 이 배열에서 원소 $3$개를 빼고 남은 것은 다 절댓값이 $10^4$인 원소로 만들 수 있기 때문에 이 합은 $(10^5 - 4) \cdot 10^4) = 10^9 - 4 \cdot 10^4)$ 이다.
그러면 나머지 3개의 원소는 어떻게 될까? 해는 각각 $-10^4, -10^4, (10^4 + 10^4)$ 이기 때문에 총 절댓값의 합은 $4 \cdot 10^4$ 이다. 즉 이 모든 값을 더하면 $10^9 - 4 \cdot 10^4 + 4 \cdot 10^4 = 10^9$ 이므로 조건을 만족한다.

정답 코드

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int t; cin >> t;
    while(t--){
        int n; cin >> n;
        int a[n];
        for(int& i : a) cin >> i;
        if(n & 1){
            if(a[0] + a[1]) cout << -a[2] << " " << -a[2] << " " << a[0] + a[1] << " ";
            else if(a[1] + a[2]) cout << a[1] + a[2] << " " << -a[0] << " " << -a[0] << " ";
            else cout << -a[1] << " " << a[0] + a[2] << " " << -a[1] << " ";
            for(int i = 3; i < n; i+=2)  cout << a[i + 1] << " " << -a[i] << " ";
        }else{
            for(int i = 0; i < n; i+=2)  cout << a[i + 1] << " " << -a[i] << " ";
        }
        cout << "\n";
    }
    return 0;
}