원신 시리즈 - Windblume Festival (G4)

문제

링크

배열이 주어지고 그 뒤에꺼를 cyclic하게 지울 수 있는 연산이 주어질 때, 나오는 최댓값은 얼마일까?

아이디어 몇 개와 풀이

1. 주어진 식의 결과는 반드시 $\sum\limits_{i=1}^{n}c_i a_i$ (단, $c_i \in [-1,1]$)를 가질 것이다. (수업 시간에 배운거에 따르면 Rademacher Variable로 봐도 되긴 한데, 넘어가자.)
2. 반드시 $c_i$들 중에서는 하나는 1, 하나는 -1임이 강제된다. (왜?) 무조건 빼기 연산을 실행하면 부호가 반전되기에, 부호가 서로 다른 두 개를 무조건 찾을 수 있다.

3. 질문: 그럼 2의 조건을 만족시키는 모든 수열이 가능한가?

4. 답: 그렇다. 증명은 귀납법으로 해보자.
   • 우선 개수가 $n=1,2$인 경우는 trivial하게 끝난다.
   • $n=k$인 경우에 대해 2의 조건을 만족시키는 모든 조합이 가능하다고 하자. 그럼 induction hypothesis를 쓰기 위해 $n=k+1$를 보면 가능한 케이스가 두 가지인데,
   • 만일 +가 2개 이상 있다면 cyclic에 의해 -+이 붙어있는 게 정수IVT적인 방식으로 존재함을 알 수 있다. 그렇다면 뒤에껄 지우는 연산을 하고 여기다 -를 붙인다면? -의 개수는 동일한데 +의 개수는 하나 줄었다. 그래도 여전히 둘 다 1개 이상이니 그 이후의 연산을 해결할 수 있다.
   • 만일 -가 2개 이상 있다면 cyclic에 의해 +-가 붙어있는 게 정수IVT적인 방식으로 존재한다. 나머지 부분은 동일하게 증명을 이어가면 된다. - 증명 완료!
5. 따라서 이런 조합 중에서 합을 최대화 시키면 된다.
6. $0$이 하나 있거나, 양수음수 조합이 섞여있다면 단순히 절댓값의 합이 될 것이다.
7. 남은 경우는 양수만 있는 경우, 음수만 있는 경우.
   • 양수만 있는 경우, 제일 작은 녀석을 합에서 두 번 지우면 된다.
   • 음수만 있는 경우, 절댓값이 제일 작은 녀석을 합에서 두 번 지우면 된다.
8. 해결!

코드

import sys
input = sys.stdin.readline
T = int(input())
for _ in range(T):
    n = int(input())
    L = list(map(int,input().split()))
    if n==1:
        print(L[0])
        continue
    abs_sum = sum(abs(i) for i in L)
    if 0 in L:
        print(abs_sum)
    elif any(x>0 for x in L) and not any(x<0 for x in L):
        print(abs_sum-2*min(L))
    elif not any(x>0 for x in L) and any(x<0 for x in L):
        min_abs = min(abs(x) for x in L)
        print(abs_sum-2*min_abs)
    else:
        print(abs_sum)

연말을 밝히는 좋은 원신 애드혹 문제였다!

그러니까 콜롬비나 제발 반천에 나와줘요..