配列操作と最適化アルゴリズムの応用

A. 順序逆転検出

要素順を変更して、新しい配列を作成し、その配列が元の配列と異なる順序になるようにする問題です。

#include <vector>
#include <iostream>
using namespace std;

void findDisorder(vector<int>& arr) {
    for (int i = 0; i < arr.size() - 1; ++i) {
        if (arr[i] > arr[i + 1]) {
            cout << "YES\n2\n" << arr[i] << ' ' << arr[i + 1] << '\n';
            return;
        }
    }
    cout << "NO\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<int> data(n);
        for (auto& elem : data) cin >> elem;
        findDisorder(data);
    }
    return 0;
}

B. 最小和計算

配列内の特定の要素を操作して、指定された条件のもとで最小値を求める問題です。

#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;

int computeMinSum(const vector<int>& arr) {
    if (arr.size() < 2) return arr[0];
    return min(arr[0] + arr[0], arr[0] + arr[1]);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<int> arr(n);
        for (auto& elem : arr) cin >> elem;
        cout << computeMinSum(arr) << '\n';
    }
    return 0;
}

C. 部分集合の乗算

配列の各要素間の除算関係を破壊するための値xを見つける問題です。

#include <vector>
#include <numeric>
#include <iostream>
using namespace std;

long long gcd(long long a, long long b) {
    while (b != 0) {
        auto temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

long long lcm(long long a, long long b) {
    return a / gcd(a, b) * b;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<long long> arr(n);
        for (auto& elem : arr) cin >> elem;
        long long result = 1;
        for (int i = 0; i < n - 1; ++i) {
            if (arr[i + 1] % arr[i] != 0) {
                result = lcm(result, arr[i] / gcd(arr[i], arr[i + 1]));
            }
        }
        cout << result << '\n';
    }
    return 0;
}

D. 回文配列作成

特定の条件に基づいて配列を回文に変換できるか判定する問題です。

#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;

bool canFormPalindrome(vector<int>& arr, int k) {
    vector<int> sortedArr = arr;
    sort(sortedArr.begin(), sortedArr.end());
    vector<int> filtered;
    for (auto val : arr) {
        if (val <= sortedArr[k - 1]) filtered.push_back(val);
    }
    int left = 0, right = filtered.size() - 1;
    while (left < right) {
        while (left < filtered.size() && filtered[left] == sortedArr[k - 1]) ++left;
        while (right >= 0 && filtered[right] == sortedArr[k - 1]) --right;
        if (left > right) return true;
        if (filtered[left] != filtered[right]) return false;
        ++left, --right;
    }
    return true;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) {
        int n, k;
        cin >> n >> k;
        vector<int> arr(n);
        for (auto& elem : arr) cin >> elem;
        cout << (canFormPalindrome(arr, k) ? "YES\n" : "NO\n");
    }
    return 0;
}