Codeforces Round 1049-C (Div. 2) Ultimate Value

최초 업로드: 2025-09-09 17:00:54

최근 수정 시간: 2025-09-09 17:00:54

카테고리: Codeforces

# C. Ultimate Value
[문제 링크](https://codeforces.com/contest/2140/problem/C)

## Problem Statement

Let's define a function $f(a)$ for an array $a$ of length $n$ as
$$
f(a)=\mathrm{cost}+(a_1-a_2+a_3-a_4\cdots a_n)
$$
where $\mathrm{cost}$ is zero initially.

Now consider the scenario where Alice and Bob are given an array $a$ of length $n$. They play a game taking at most $10^{100}$ turns alternately with Alice going first.

In each turn, they must perform any **one** (only one) of the following operations:

- End the game for both Alice and Bob.
- Choose two indices $l,r$ with $1 \le l \le r \le n$ and swap $a_l$ and $a_r$; this adds $(r-l)$ to the $\mathrm{cost}$.

Assume that Alice tries to maximize $f(a)$ and Bob tries to minimize it.

Your task is to determine the final value of $f(a)$ assuming both players play optimally.

## Input
Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each test case contains a single integer $n$ ($1 \le n \le 2\cdot10^5$) — the length of the array $a$.

The second line contains $n$ integers $a_1,a_2,a_3,\ldots,a_n$ ($1 \le a_i \le 10^9$) — the elements of the array $a$.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2\cdot10^5$.

## Output
For each testcase, output a single integer — the final value of $f(a)$ assuming both players play optimally.

## 풀이
Alice는 최대한 cost를 높이면서 바꾸는 것이 이득이고, Bob은 무조건 멈추는게 이득이다. 따라서 이 게임은 최대 1번의 Swap이 발생한다. 가장 우선순위가 높은 짝수 번째와 홀수 번째의 원소를 기록해놓고 Alice가 한번의 Swap으로 얻을 수 있는 최대 Cost를 계산하였다.

``` c++
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

ll a[200'001];

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int t; cin >> t;
    while(t--) {
        int n; cin >> n;

ll sum=0;
        for(int i=1;i<=n;i++) {
            cin >> a[i];
            if(i%2==1) sum += a[i];
            else sum -= a[i];
        }

ll plus=0;
        if(n>=2) plus = max((ll)(1-2*a[1]+2*a[2]), (ll)((n-1)/2*2));
        ll minOdd=a[1], maxEven=a[2], oddIdx=1, evenIdx=2;
        for(int i=3;i<=n;i++) {
            if(i%2==1) {
                plus = max(plus, i-evenIdx - 2*a[i] + 2*maxEven);
                if(2*minOdd+oddIdx > 2*a[i]+i) {
                    minOdd = a[i];
                    oddIdx = i;
                }
            } else {
                plus = max(plus, i-oddIdx - 2*minOdd + 2*a[i]);
                if(2*maxEven-evenIdx < 2*a[i]-i) {
                    maxEven = a[i];
                    evenIdx = i;
                }
            }
        }
        cout << sum+max(plus, 0LL) << '\n';
    }
}
```