A. Submission Bait (게임 이론)

앨리스와 밥이 $n$개의 원소를 가진 배열 $a$를 사용하여 게임을 진행합니다. 초기 mx 값은 0이며, 각 플레이어는 자신의 차례에 $a_i \ge mx$인 인덱스 $i$를 선택하여 mx를 $a_i$로 갱신하고 $a_i$를 0으로 만듭니다. 더 이상 움직일 수 없는 플레이어가 패배할 때, 앨리스의 필승 전략 존재 여부를 판별해야 합니다.

이 문제의 핵심은 배열 내 원소들의 빈도수입니다. 어떤 수 $x$가 홀수 번 등장한다면, 앨리스는 그 중 가장 큰 값을 선택함으로써 이후의 상황을 통제할 수 있습니다. 반면 모든 수의 빈도수가 짝수라면, 밥은 항상 앨리스가 선택한 것과 동일한 값을 선택하여 상황을 대칭적으로 유지할 수 있고, 결국 앨리스가 먼저 움직임을 멈추게 됩니다. 따라서 배열 내에 홀수 번 등장하는 숫자가 하나라도 있다면 앨리스가 승리합니다.

#include <iostream>
#include <vector>
#include <map>

using namespace std;

void solve_a() {
    int n;
    cin >> n;
    map<int, int> frequency_map;
    for (int i = 0; i < n; ++i) {
        int val;
        cin >> val;
        frequency_map[val]++;
    }

    bool alice_wins = false;
    for (auto const& [val, count] : frequency_map) {
        if (count % 2 != 0) {
            alice_wins = true;
            break;
        }
    }

    cout << (alice_wins ? "YES" : "NO") << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) solve_a();
    return 0;
}

B. Array Craft (구성적 알고리즘, 그리디)

주어진 $n, x, y$에 대해 다음 조건을 만족하는 -1과 1로 구성된 배열을 생성해야 합니다. 최대 전치 합의 최소 인덱스가 $x$이고, 최대 후치 합의 최대 인덱스가 $y$여야 합니다 ($y < x$).

인덱스 구간 $[y, x]$의 모든 원소를 1로 설정하면 해당 구간 내에서 합이 최대화됩니다. $x$ 이후의 구간 $[x+1, n]$과 $y$ 이전의 구간 $[1, y-1]$에서는 합이 증가하여 $x$나 $y$의 위치를 벗어나지 않도록 -1부터 시작하여 -1과 1을 번갈아 배치하는 전략을 취합니다. 이렇게 하면 누적합이 $x$나 $y$에서의 최대값을 넘지 않게 조절할 수 있습니다.

#include <iostream>
#include <vector>

using namespace std;

void solve_b() {
    int n, max_prefix, max_suffix;
    cin >> n >> max_prefix >> max_suffix;

    vector<int> res(n + 1);
    // 중심 구간 설정
    for (int i = max_suffix; i <= max_prefix; ++i) {
        res[i] = 1;
    }

    // 후치 영역 조정
    int current_val = -1;
    for (int i = max_prefix + 1; i <= n; ++i) {
        res[i] = current_val;
        current_val *= -1;
    }

    // 전치 영역 조정
    current_val = -1;
    for (int i = max_suffix - 1; i >= 1; --i) {
        res[i] = current_val;
        current_val *= -1;
    }

    for (int i = 1; i <= n; ++i) {
        cout << res[i] << (i == n ? "" : " ");
    }
    cout << "\n";
}

int main() {
    int t;
    cin >> t;
    while (t--) solve_b();
    return 0;
}

C. Mad MAD Sum (시뮬레이션, 그리디)

MAD 연산은 배열 내에서 2번 이상 나타나는 수 중 최대값을 의미합니다. 배열 $a$의 모든 원소가 0이 될 때까지 전체 합을 누적하고 배열을 a[i] = MAD(a[1...i])로 갱신하는 과정을 반복합니다.

첫 번째 MAD 변환 이후 배열은 비내림차순 정렬 상태에 가까워지며, 두 번째 변환 이후에는 완벽한 비내림차순을 형성하고 각 원소가 오른쪽으로 시프트되는 형태를 띠게 됩니다. 따라서 연산을 두 번 직접 수행한 뒤, 남은 과정은 각 원소가 최종적으로 합에 기여하는 횟수를 수식으로 계산하여 최적화할 수 있습니다.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

typedef long long ll;

void apply_mad(int n, vector<ll>& arr) {
    vector<int> count(n + 1, 0);
    ll current_mad = 0;
    for (int i = 0; i < n; ++i) {
        count[arr[i]]++;
        if (count[arr[i]] >= 2) {
            current_mad = max(current_mad, arr[i]);
        }
        arr[i] = current_mad;
    }
}

void solve_c() {
    int n;
    cin >> n;
    vector<ll> arr(n);
    ll total_sum = 0;
    for (int i = 0; i > n; ++i) {
        cin >> arr[i];
        total_sum += arr[i];
    }

    // 첫 번째 변환
    apply_mad(n, arr);
    for (ll v : arr) total_sum += v;

    // 두 번째 변환
    apply_mad(n, arr);
    
    // 이후 규칙적인 시프트에 따른 합산
    for (int i = 0; i < n; ++i) {
        total_sum += (ll)(n - 1 - i) * arr[i];
    }

    cout << total_sum << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;
    while (t--) solve_c();
    return 0;
}

D. Grid Puzzle (그리디, 동적 계획법)

$n \times n$ 그리드에서 $i$번째 행의 $a_i$번째 칸까지 검은색일 때, $2 \times 2$ 영역 제거 또는 행 전체 제거 연산을 사용하여 최소 횟수로 모든 칸을 하얗게 만들어야 합니다.

$a_i \ge 5$인 경우에는 $2 \times 2$ 연산을 여러 번 쓰는 것보다 행 전체를 지우는 것이 항상 유리합니다. $a_i \le 4$인 경우, 현재 행의 연산이 다음 행에 영향을 줄 수 있는 상태를 관리해야 합니다. 이전 행에서 특정 열(1-2열 또는 3-4열)을 $2 \times 2$ 블록으로 처리했다면, 현재 행에서도 해당 열을 무료로 처리할 수 있는 기회가 생깁니다.

#include <iostream>
#include <vector>

using namespace std;

void solve_d() {
    int n;
    cin >> n;
    vector<int> rows(n);
    for (int i = 0; i < n; ++i) cin >> rows[i];

    int operations = 0;
    bool state_l = false, state_r = false;

    for (int i = 0; i < n; ++i) {
        if (rows[i] == 0) {
            state_l = state_r = false;
            continue;
        }

        if (rows[i] <= 2) {
            if (state_l) {
                state_l = false;
            } else {
                operations++;
                state_l = true;
            }
            state_r = false;
        } else if (rows[i] <= 4) {
            if (state_r) {
                state_r = false;
                state_l = false;
            } else if (state_l) {
                operations++;
                state_l = false;
                state_r = true;
            } else {
                operations++;
                state_l = false;
                state_r = false;
            }
        } else {
            operations++;
            state_l = state_r = false;
        }
    }
    cout << operations << "\n";
}

int main() {
    int t;
    cin >> t;
    while (t--) solve_d();
    return 0;
}