이 문서는 Codeforces Round 920 (Div. 3)의 문제 D, E, F에 대한 해결 전략과 C++ 코드 예시를 제공합니다.

문제 D: 절댓값 합 최대화

문제 설명: 두 개의 배열 A와 B가 주어졌을 때, 각 배열에서 하나의 요소를 뽑아 쌍을 이루고, 이 과정에서 만들어지는 모든 쌍의 요소들의 절댓값 차이의 합을 최대화해야 합니다. 모든 요소는 단 한 번만 사용될 수 있습니다.

해결 전략:

이 문제는 그리디 알고리즘으로 해결할 수 있습니다. 배열 A와 B를 각각 오름차순으로 정렬한 후, 두 포인터를 사용하여 다음과 같은 전략을 반복합니다.

1. A의 가장 작은 값(A[0])과 B의 가장 큰 값(B[m-1])을 짝지었을 때의 절댓값 차이를 계산합니다.
2. A의 가장 큰 값(A[n-1])과 B의 가장 작은 값(B[0])을 짝지었을 때의 절댓값 차이를 계산합니다.
3. 두 경우 중 절댓값 차이가 더 큰 쪽을 선택하여 총 합에 더하고, 선택된 두 요소를 배열에서 제거합니다 (혹은 해당 요소들을 가리키는 포인터를 이동시킵니다).

이 과정을 배열 중 하나가 비어질 때까지 반복하면 최대 절댓값 합을 얻을 수 있습니다. 각 단계에서 가장 큰 이득을 취하는 것이 전체 최적 해로 이어지는 그리디 속성이 이 문제에 적용됩니다.

C++ 코드 예시:

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

void solve_d() {
    int n_a, m_b; 
    std::cin >> n_a >> m_b;
    std::vector<long long> arr_a(n_a);
    std::vector<long long> arr_b(m_b);

    for (auto &val : arr_a) std::cin >> val;
    for (auto &val : arr_b) std::cin >> val;

    std::sort(arr_a.begin(), arr_a.end());
    std::sort(arr_b.begin(), arr_b.end());

    long long total_max_diff = 0;
    int left_a = 0, right_a = n_a - 1;
    int left_b = 0, right_b = m_b - 1;

    while (left_a <= right_a) {
        // Option 1: A의 최소값과 B의 최대값
        long long diff1 = std::abs(arr_a[left_a] - arr_b[right_b]);
        // Option 2: A의 최대값과 B의 최소값
        long long diff2 = std::abs(arr_a[right_a] - arr_b[left_b]);

        if (diff1 >= diff2) {
            total_max_diff += diff1;
            left_a++;
            right_b--;
        } else {
            total_max_diff += diff2;
            right_a--;
            left_b++;
        }
    }

    std::cout << total_max_diff << std::endl;
}   

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

문제 E: 격자 게임 전략

문제 설명: H x W 크기의 격자에서 앨리스(xa, ya)와 밥(xb, yb)이 게임을 합니다. 앨리스는 위로만, 밥은 아래로만 이동할 수 있으며, 벽에 부딪히면 반대 방향으로 튕겨 나갈 수 있습니다. 앨리스가 먼저 움직이고, 한 턴에 한 칸씩 이동합니다. 최종적으로 누가 상대를 잡을 수 있는지 또는 무승부인지 결정해야 합니다.

해결 전략:

이 게임은 앨리스와 밥의 상대적인 위치와 이동 횟수에 따라 승패가 결정됩니다.

1. 초기 위치 특수 처리: 만약 앨리스의 현재 행(xa)이 밥의 현재 행(xb)보다 같거나 크다면, 앨리스는 위로만 움직일 수 있으므로 밥을 잡을 수 없습니다. 이 경우 항상 "Draw"입니다.
2. 남은 행 차이 계산: row_diff = xb - xa. 이 값은 앨리스가 밥을 잡기 위해 이동해야 하는 최소 세로 칸 수입니다.
3. 이동 횟수 분석: 앨리스가 먼저 움직이므로, row_diff가 짝수일 때와 홀수일 때 각 플레이어에게 주어지는 턴 수가 달라집니다.
   • row_diff가 홀수일 경우: 앨리스가 (row_diff + 1) / 2번 이동하고, 밥은 (row_diff - 1) / 2번 이동합니다. (앨리스의 턴이 1회 더 많음)
   • row_diff가 짝수일 경우: 앨리스와 밥 모두 row_diff / 2번 이동합니다. (앨리스와 밥의 턴 수가 동일)
4. 승패 조건: 각 플레이어는 자신의 턴 수 내에 상대방의 가로 위치로 이동해야 합니다. 이때 벽에 부딪혀 반대 방향으로 움직이는 것을 고려해야 합니다.
   • 앨리스의 턴 (row_diff가 홀수일 때): 앨리스에게 주어진 턴 수를 alice_moves = (row_diff + 1) / 2라고 할 때,
     • 만약 abs(ya - yb) <= alice_moves이면 앨리스는 밥과 같은 열에 도달할 수 있습니다.
     • 또는 앨리스가 밥에게 도달하기 전에 벽에 닿아 튕겨 나올 수 있습니다.
       • ya < yb일 때: 앨리스가 오른쪽 벽(W)까지 이동하고 다시 돌아와 밥을 잡을 수 있는지 확인합니다. (W - ya) + (W - yb) <= alice_moves
       • ya > yb일 때: 앨리스가 왼쪽 벽(1)까지 이동하고 다시 돌아와 밥을 잡을 수 있는지 확인합니다. (ya - 1) + (yb - 1) <= alice_moves
     • 위 조건 중 하나라도 만족하면 앨리스가 이깁니다.
   • 밥의 턴 (row_diff가 짝수일 때): 밥에게 주어진 턴 수를 bob_moves = row_diff / 2라고 할 때,
     • 만약 ya == yb이면 밥은 앨리스와 같은 열에 이미 있으므로 이깁니다.
     • 또는 밥이 앨리스에게 도달하기 전에 벽에 닿아 튕겨 나올 수 있습니다.
       • yb < ya일 때: 밥이 오른쪽 벽(W)까지 이동하고 다시 돌아와 앨리스를 잡을 수 있는지 확인합니다. (W - yb) + (W - ya) <= bob_moves
       • yb > ya일 때: 밥이 왼쪽 벽(1)까지 이동하고 다시 돌아와 앨리스를 잡을 수 있는지 확인합니다. (yb - 1) + (ya - 1) <= bob_moves
     • 위 조건 중 하나라도 만족하면 밥이 이깁니다.
5. 위의 어떤 조건도 만족하지 않으면 "Draw"입니다.

C++ 코드 예시:

#include <iostream>
#include <algorithm> // For std::abs

void solve_e() {
    int grid_h, grid_w;
    int alice_r, alice_c, bob_r, bob_c;
    std::cin >> grid_h >> grid_w >> alice_r >> alice_c >> bob_r >> bob_c;

    // 앨리스가 이미 밥의 행보다 같거나 아래에 있다면 앨리스는 밥을 잡을 수 없음
    if (alice_r >= bob_r) {
        std::cout << "Draw\n";
        return;
    }

    int row_diff = bob_r - alice_r; // 앨리스가 밥에게 도달하기 위해 필요한 행 이동 수

    if (row_diff % 2 == 1) { // 앨리스 턴이 밥보다 한 번 더 많음
        int alice_moves = (row_diff + 1) / 2; // 앨리스가 사용할 수 있는 가로 이동 턴 수

        bool alice_can_win = false;
        // 1. 직접 밥에게 도달
        if (std::abs(alice_c - bob_c) <= alice_moves) {
            alice_can_win = true;
        }
        // 2. 오른쪽 벽을 이용하여 밥에게 도달
        if (alice_c < bob_c) {
            // 앨리스가 오른쪽 벽에 닿은 후 되돌아와 밥을 잡을 수 있는 경우
            if ((grid_w - alice_c) + (grid_w - bob_c) <= alice_moves) {
                alice_can_win = true;
            }
        }
        // 3. 왼쪽 벽을 이용하여 밥에게 도달
        else if (alice_c > bob_c) {
            // 앨리스가 왼쪽 벽에 닿은 후 되돌아와 밥을 잡을 수 있는 경우
            if ((alice_c - 1) + (bob_c - 1) <= alice_moves) {
                alice_can_win = true;
            }
        }
        
        if (alice_can_win) {
            std::cout << "Alice\n";
        } else {
            std::cout << "Draw\n";
        }

    } else { // 앨리스와 밥의 턴 수가 동일
        int bob_moves = row_diff / 2; // 밥이 사용할 수 있는 가로 이동 턴 수

        bool bob_can_win = false;
        // 1. 밥이 앨리스와 같은 열에 이미 있다면
        if (alice_c == bob_c) {
            bob_can_win = true;
        }
        // 2. 오른쪽 벽을 이용하여 앨리스에게 도달
        if (bob_c < alice_c) {
            // 밥이 오른쪽 벽에 닿은 후 되돌아와 앨리스를 잡을 수 있는 경우
            if ((grid_w - bob_c) + (grid_w - alice_c) <= bob_moves) {
                bob_can_win = true;
            }
        }
        // 3. 왼쪽 벽을 이용하여 앨리스에게 도달
        else if (bob_c > alice_c) {
            // 밥이 왼쪽 벽에 닿은 후 되돌아와 앨리스를 잡을 수 있는 경우
            if ((bob_c - 1) + (alice_c - 1) <= bob_moves) {
                bob_can_win = true;
            }
        }

        if (bob_can_win) {
            std::cout << "Bob\n";
        } else {
            std::cout << "Draw\n";
        }
    }
}   

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

문제 F: 가중치 접두사 합과 제곱근 분할

해결 전략:

문제 F는 특정 유형의 쿼리나 업데이트를 효율적으로 처리하기 위한 고급 자료 구조 및 알고리즘 기법을 요구합니다. "가중치 접두사 합" (Weighted Prefix Sum)과 "제곱근 분할" (Square Root Decomposition)은 이러한 문제들을 해결하는 데 자주 사용되는 강력한 조합입니다.

• 가중치 접두사 합: 일반적인 접두사 합은 배열의 특정 인덱스까지의 요소들의 합을 빠르게 계산합니다. 가중치 접두사 합은 각 요소에 특정 가중치를 곱한 후의 합을 계산하는 것입니다. 이는 구간 합(range sum) 쿼리에서 매우 효율적이며, 쿼리가 들어올 때마다 전체 구간을 다시 계산할 필요 없이 O(1) 시간에 특정 지점까지의 누적 합을 얻을 수 있습니다.
• 제곱근 분할: 배열이나 데이터 구조를 일정 크기의 블록들로 나누는 기법입니다. 블록의 크기는 보통 전체 데이터 크기 N의 제곱근(sqrt(N))으로 설정합니다. 이 방법은 전체 데이터에 대한 업데이트(단일 요소 또는 작은 구간)와 큰 구간에 대한 쿼리(여러 블록에 걸친)를 균형 있게 처리할 때 유용합니다.
  • 업데이트: 단일 요소를 업데이트할 경우, 해당 요소가 속한 블록의 정보만 갱신하고, 전체 블록의 정보는 나중에 필요할 때 지연 갱신하거나 O(sqrt(N)) 시간에 업데이트할 수 있습니다.
  • 쿼리: 특정 범위 [L, R]에 대한 쿼리가 들어오면, 이 범위는 몇 개의 완전한 블록과 시작 및 끝 부분에 걸쳐 있는 불완전한 블록들로 나눌 수 있습니다. 완전한 블록들은 미리 계산된 정보를 O(1)에 활용하고, 불완전한 블록들은 직접 순회하며 계산하여 O(sqrt(N)) 시간에 쿼리를 처리합니다.

이 두 가지 기법을 함께 사용하면, 예를 들어 배열에 대한 값 변경이 자주 일어나고 동시에 특정 가중치가 적용된 구간 합을 빠르게 조회해야 하는 문제에서 효과적인 해결책을 제공할 수 있습니다. 시간 복잡도는 보통 O(sqrt(N)) 또는 O(sqrt(N) log N) 수준으로 유지됩니다.