A. False Alarm

문제의 지시에 따라 직접 구현하면 됩니다. 1이 등장하는 위치들을 기록하고, 인접한 1들 사이의 거리를 누적하여 총 소요 시간을 계산합니다.

정답 코드:

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int tc;
    cin >> tc;
    while (tc--) {
        int len, limit;
        cin >> len >> limit;
        
        vector<int> pos;
        for (int i = 1; i <= len; i++) {
            int val;
            cin >> val;
            if (val == 1) pos.push_back(i);
        }
        
        long long total = 1;
        for (size_t i = 1; i < pos.size(); i++) {
            total += pos[i] - pos[i-1];
        }
        
        cout << (total <= limit ? "Yes" : "No") << '\n';
    }
    return 0;
}

B. Shrink

관찰을 통해 규칙을 찾는 구성 문제입니다. 1과 2를 배열의 양 끝에 배치하고, 중앙에는 n을, 나머지 위치에는 적절한 값을 배치하면 최대한 많은 수축 연산을 수행할 수 있습니다.

정답 코드:

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int tc;
    cin >> tc;
    while (tc--) {
        int n;
        cin >> n;
        
        vector<int> res(n + 1);
        int center = (n + 1) / 2;
        
        for (int i = 1; i <= n; i++) {
            if (i == 1) res[i] = 1;
            else if (i == n) res[i] = 2;
            else if (i == center) res[i] = n;
            else if (i == 2) res[i] = center;
            else res[i] = i;
        }
        
        for (int i = 1; i <= n; i++) {
            cout << res[i] << " \n"[i == n];
        }
    }
    return 0;
}

C. Cool Partition

배열을 여러 구간으로 분할하는 문제입니다. 핵심 관찰은 다음과 같습니다: 구간 [l, r]이 유효한 분할이 되려면, 해당 구간이 [1, r]에 등장하는 모든 서로 다른 원소를 포함해야 합니다.

최대 분할 개수를 구하기 위해, 현재 위치까지의 원소 집합이 전체 원소 집합과 같아지는 순간마다 구간을 어주면 됩니다. 이는 각 구간의 길이를 최소화하여 구간 개수를 최대화하는 전략입니다.

정답 코드:

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int tc;
    cin >> tc;
    while (tc--) {
        int n;
        cin >> n;
        
        vector<int> arr(n);
        for (int i = 0; i < n; i++) cin >> arr[i];
        
        unordered_set<int> prefix, total;
        int partitions = 0;
        
        for (int x : arr) {
            prefix.insert(x);
            total.insert(x);
            if (prefix.size() == total.size()) {
                partitions++;
                prefix.clear();
            }
        }
        
        cout << partitions << '\n';
    }
    return 0;
}

D. Retaliation

연립방정식을 푸는 수학 문제입니다. 각 원소 a[i]가 0이 되기 위해 필요한 두 가지 연산의 횟수를 변수로 설정합니다.

첫 번째 원소는 x + n·y, 두 번째 원소는 2x + (n-1)·y만큼 소합니다. 이를 연립하여:

• a₁ - a₂ = y - x
• x = y - a₁ + a₂

첫 번째 식에 대입하면 y = (2a₁ - a₂) / (n+1)을 얻습니다. x와 y가 모두 음이 아닌 정수이고, 모든 원소가 정확히 0이 되는지 검증하면 됩니다.

정답 코드:

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int tc;
    cin >> tc;
    while (tc--) {
        int n;
        cin >> n;
        
        vector<ll> val(n);
        for (int i = 0; i < n; i++) cin >> val[i];
        
        ll y = (2 * val[0] - val[1]) / (n + 1);
        ll x = y - val[0] + val[1];
        
        if (x < 0 || y < 0) {
            cout << "No\n";
            continue;
        }
        
        bool valid = true;
        for (int i = 0; i < n; i++) {
            ll remain = val[i] - x * (i + 1) - y * (n - i);
            if (remain != 0) {
                valid = false;
                break;
            }
        }
        
        cout << (valid ? "Yes" : "No") << '\n';
    }
    return 0;
}