A 문제

첫 번째 위치의 기여도는 항상 0이다. 나머지 n-1개의 위치에서 최대값과 최소값을 첫 두 위치에 배치하면 최적의 결과를 얻을 수 있다. 이 경우 기여도는 (최대값 - 최소값) × (n-1)이 된다.

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;

void process() {
    int length;
    cin >> length;
    
    int high = INT_MIN, low = INT_MAX;
    for (int idx = 0; idx < length; idx++) {
        int value;
        cin >> value;
        high = max(high, value);
        low = min(low, value);
    }
    
    cout << (high - low) * (length - 1) << '\n';
}

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

B 문제

서로 다른 위치의 0과 1로 구성된 부분수열은 모두 다르게 취급된다. 하나의 1만 존재할 때가 가장 작은 값을 가지며, 그 값은 1이다.

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

void handle() {
    int size;
    cin >> size;
    
    cout << 1;
    for (int i = 1; i < size; i++) {
        cout << 0;
    }
    cout << '\n';
}

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

C 문제

문제 조건을 정확히 이해해야 한다. 1의 좌우가 모두 0일 때만 AND 연산으로 1을 제거할 수 있다. 따라서 문자열의 시작이나 끝이 1이거나, 연속된 두 개의 1이 존재하면 "YES"를 출력한다.

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

void execute() {
    int len;
    string sequence;
    cin >> len >> sequence;
    
    bool valid = false;
    
    // 시작이나 끝이 1인지 확인
    if (sequence[0] == '1' || sequence[len-1] == '1') {
        valid = true;
    }
    
    // 연속된 1이 있는지 확인
    for (int i = 0; i < len - 1; i++) {
        if (sequence[i] == '1' && sequence[i+1] == '1') {
            valid = true;
            break;
        }
    }
    
    cout << (valid ? "YES" : "NO") << '\n';
}

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

D 문제

'L'과 'R'은 각각 왼쪽 이동과 오른쪽 이동을 의미하며, 한 방향 이동만 고려해도 충분하다.

'RRR...LLL...' 형태의 부분문자열 [l,r]에서 pi(l ≤ i ≤ r)는 [l,r] 범위 내 임의의 위치로 이동 가능하므로 순서를 자유롭게 재배치할 수 있다. 이러한 부분문자열들이 전체 문자열 s를 구성한다.

인덱스 i에서 s_i='L'이고 s_{i+1}='R'인 경우 i 위치에 분기점이 생긴다. 즉, [1,i] 범위의 숫자들은 [i+1,n] 위치로 이동할 수 없다. 오른쪽 이동만 고려할 때, 모든 [l,r] 구간의 최대값이 r보다 작거나 같아야 유효한 시퀀스가 된다.

각 'L''R' 쌍(인덱스 i와 i+1)에 대해 [1,i] 구간의 최대값이 i보다 크면 불가능하다. 이러한 불법적인 'L''R' 쌍의 개수 cnt를 세고, 0이면 "YES"를 출력한다.

수정 작업의 영향을 고려할 때, 변경 전후가 'L''R'인지 확인하고 cnt를 업데이트하면 된다. 전처리로 누적 최대값만 계산하면 된다.

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
const int MAX = 200005;

void task() {
    int n, q;
    cin >> n >> q;
    
    vector<int> values(n + 1);
    vector<int> prefix_max(n + 1, 0);
    
    for (int i = 1; i <= n; i++) {
        cin >> values[i];
        prefix_max[i] = max(prefix_max[i-1], values[i]);
    }
    
    string commands;
    cin >> commands;
    commands = "0" + commands;
    
    int invalid_count = 0;
    
    for (int i = 1; i < n; i++) {
        if (commands[i] == 'L' && commands[i+1] == 'R') {
            if (prefix_max[i] > i) {
                invalid_count++;
            }
        }
    }
    
    while (q--) {
        int pos;
        cin >> pos;
        
        char old_char = commands[pos];
        commands[pos] = (old_char == 'L') ? 'R' : 'L';
        
        // 변경된 위치 주변의 유효성 검사 업데이트
        if (old_char == 'L') {
            // L->R 변경
            if (pos + 1 <= n && commands[pos+1] == 'R' && prefix_max[pos] > pos) {
                invalid_count--;
            }
            if (pos - 1 >= 1 && commands[pos-1] == 'L' && prefix_max[pos-1] > pos-1) {
                invalid_count++;
            }
        } else {
            // R->L 변경
            if (pos - 1 >= 1 && commands[pos-1] == 'L' && prefix_max[pos-1] > pos-1) {
                invalid_count--;
            }
            if (pos + 1 <= n && commands[pos+1] == 'R' && prefix_max[pos] > pos) {
                invalid_count++;
            }
        }
        
        cout << (invalid_count == 0 ? "YES" : "NO") << '\n';
    }
}

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