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\ne 0)$ 가 주어진다.

Output
각 테스트 케이스마다 원소 $n$개 $b_1,b_2,...,b_n(|b_1|+|b_2|+...+|b_n|\le {10}^9,b_i\ne 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_{1}x+a_{2}y+a_{3}z=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;
}