問題A：連続要素の除去

この問題では、与えられたシーケンスから連続する重複要素を除去する必要があります。

解法：連続する同じ要素を1つにまとめることで、シーケンスの長さを最小化します。

#include <iostream>
#include <vector>

using namespace std;

typedef long long ll;

void process() {
    int elements;
    cin >> elements;
    
    vector<int> sequence;
    for (int i = 0; i < elements; i++) {
        int value;
        cin >> value;
        if (sequence.empty() || value != sequence.back()) {
            sequence.push_back(value);
        }
    }
    
    cout << sequence.size() << "\n";
}

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

問題B：最適化された記録修正

この問題では、記録の削除または交換によってシーケンスを合法的にし、コストを最小化する必要があります。

解法：動的計画法を使用して、各記録に対する3つの状態を管理します。

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

using namespace std;

typedef long long ll;

void solve() {
    int records;
    ll cost[3] = {0};
    cin >> records >> cost[1] >> cost[2];
    
    vector<pair<int, int>> data(records);
    for (auto &entry : data) {
        cin >> entry.first >> entry.second;
    }
    
    const ll INF = 1e16;
    vector<vector<ll>> dp(records, vector<ll>(3, INF));
    dp[0][0] = 0;
    dp[0][1] = cost[1];
    dp[0][2] = cost[2];
    
    for (int i = 1; i < records; i++) {
        dp[i][0] = cost[1] * i;
        for (int j = 0; j < i; j++) {
            if (data[i].first >= data[j].first && data[i].second >= data[j].second) {
                dp[i][0] = min(dp[i][0], dp[j][0] + cost[1] * (i - 1 - j));
            }
            if (data[i].first >= data[j].second && data[i].second >= data[j].first) {
                dp[i][0] = min(dp[i][0], dp[j][2] + cost[1] * (i - 1 - j));
            }
        }
        
        dp[i][1] = cost[1] * (i + 1);
        for (int j = 0; j < i; j++) {
            dp[i][1] = min(dp[i][1], min({dp[j][0], dp[j][1], dp[j][2]}) + cost[1] * (i - j));
        }
        
        dp[i][2] = cost[1] * i + cost[2];
        for (int j = 0; j < i; j++) {
            if (data[i].second >= data[j].first && data[i].first >= data[j].second) {
                dp[i][2] = min(dp[i][2], dp[j][0] + cost[1] * (i - 1 - j) + cost[2]);
            }
            if (data[i].second >= data[j].second && data[i].first >= data[j].first) {
                dp[i][2] = min(dp[i][2], dp[j][2] + cost[1] * (i - 1 - j) + cost[2]);
            }
        }
    }
    
    cout << min({dp[records - 1][0], dp[records - 1][1], dp[records - 1][2]}) << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int testCases;
    cin >> testCases;
    while (testCases--) {
        solve();
    }
    
    return 0;
}

問題C：数列の合計

この問題では、特定の数列の合計を計算する必要があります。

解法：数列のパターンを分析し、数式で解を求めます。

#include <iostream>
#include <cmath>

using namespace std;

typedef long long ll;

void calculate() {
    ll value;
    cin >> value;
    
    auto logBase2 = [](ll num) -> ll {
        return log2(num);
    };
    
    cout << 2 * (value + logBase2(value + logBase2(value))) << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int testCases;
    cin >> testCases;
    while (testCases--) {
        calculate();
    }
    
    return 0;
}

問題F：最適面接順序

この問題では、面接の順序を調整して、得られる最高の年収を最大化する必要があります。

解法：企業を基準値でソートし、動的計画法を適用して最適な年収を計算します。

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

using namespace std;

typedef long long ll;

void optimize() {
    int companies;
    cin >> companies;
    
    vector<pair<int, int>> offers(companies);
    for (auto &offer : offers) {
        cin >> offer.first >> offer.second;
    }
    
    sort(offers.begin(), offers.end());
    
    vector<int> maxSalary(companies);
    for (int i = 0; i < companies; i++) {
        if (i > 0) {
            maxSalary[i] = max(maxSalary[i - 1], offers[i - 1].first + offers[i - 1].second);
        }
        maxSalary[i] = max(maxSalary[i], offers[i].first);
        if (i > 0 && maxSalary[i - 1] >= offers[i].first) {
            maxSalary[i] = max(maxSalary[i], offers[i].first + offers[i].second);
        }
    }
    
    cout << maxSalary[companies - 1] << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int testCases;
    cin >> testCases;
    while (testCases--) {
        optimize();
    }
    
    return 0;
}

問題H：特殊な順列の構築

この問題では、特定の条件を満たす順列を構築する必要があります。

解法：区間の長さの偶奇に基づいて、異なる構造の順列を生成します。

#include <iostream>
#include <vector>

using namespace std;

typedef long long ll;

void construct() {
    int size, queries;
    cin >> size >> queries;
    
    vector<int> leftBound(queries), rightBound(queries), positions(queries);
    for (int i = 0; i < queries; i++) {
        cin >> leftBound[i] >> rightBound[i] >> positions[i];
    }
    
    if ((rightBound[0] - leftBound[0]) % 2) {
        for (int i = size; i >= 1; i--) {
            cout << i << " ";
        }
    } else {
        for (int i = 1; i <= size; i += 2) {
            if (i < size) {
                cout << size - i << " " << size - i + 1 << " ";
            } else {
                cout << "1 ";
            }
        }
    }
    cout << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int testCases;
    cin >> testCases;
    while (testCases--) {
        construct();
    }
    
    return 0;
}

問題I：順列の検証

この問題では、構築された順列が特定の条件を満たすかどうかを検証する必要があります。

解法：フェニック木（バイナリインデックスツリー）を使用して、特定の値以下の要素の数を効率的に数えます。

#include <iostream>
#include <vector>

using namespace std;

typedef long long ll;

template<typename T>
class FenwickTree {
private:
    int size;
    vector<T> tree;
    
public:
    FenwickTree() {}
    FenwickTree(int n) {
        this->size = n;
        tree.resize(n + 1);
    }
    
    void addValue(int index, T value) {
        for (; index <= size; index += index & -index) {
            tree[index] += value;
        }
    }
    
    T getPrefixSum(int index) {
        T result = 0;
        for (; index > 0; index -= index & -index) {
            result += tree[index];
        }
        return result;
    }
};

void verify() {
    int length, queries;
    cin >> length >> queries;
    
    vector<int> permutation(length + 1);
    for (int i = 1; i <= length; i++) {
        cin >> permutation[i];
    }
    
    vector<int> results(queries + 1);
    vector<vector<array<int, 3>>> queryPoints(length + 1);
    
    for (int i = 1; i <= queries; i++) {
        int left, right, target;
        cin >> left >> right >> target;
        queryPoints[left - 1].push_back({-1, permutation[target], i});
        queryPoints[right].push_back({1, permutation[target], i});
        results[i] += left - 1;
    }
    
    FenwickTree<int> fenwick(length + 1);
    for (int i = 1; i <= length; i++) {
        fenwick.addValue(permutation[i], 1);
        for (auto &[sign, value, id] : queryPoints[i]) {
            results[id] += sign * fenwick.getPrefixSum(value);
        }
    }
    
    for (int i = 1; i <= queries; i++) {
        cout << results[i] << "\n";
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int testCases;
    cin >> testCases;
    while (testCases--) {
        verify();
    }
    
    return 0;
}

問題J：最適な研磨戦略

この問題では、研磨と攻撃の最適な組み合わせを見つけて、与えられたターン数で最大のダメージを計算する必要があります。

解法：研磨回数を変化させながら、各シナリオでの総ダメージを計算し、最大値を見つけます。

#include <iostream>
#include <algorithm>

using namespace std;

typedef long long ll;

void maximizeDamage() {
    ll turns, basePower, maxGrinds;
    cin >> turns >> basePower >> maxGrinds;
    
    ll optimalDamage = 0;
    ll grindLimit = min(maxGrinds, turns);
    
    for (int grinds = 0; grinds <= grindLimit; grinds++) {
        ll currentDamage = 0;
        currentDamage += (basePower + 1) * min(maxGrinds, turns);
        
        if (maxGrinds < turns) {
            currentDamage += basePower * (basePower + 1) / 2;
            ll remainingAttacks = min(turns - maxGrinds, basePower);
            currentDamage -= (basePower - remainingAttacks) * (basePower - remainingAttacks + 1) / 2;
        }
        
        turns--;
        maxGrinds--;
        basePower++;
        optimalDamage = max(optimalDamage, currentDamage);
    }
    
    cout << optimalDamage << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int testCases;
    cin >> testCases;
    while (testCases--) {
        maximizeDamage();
    }
    
    return 0;
}

問題K：ページめくりの検証

この問題では、ページめくり操作が有効かどうかを判断する必要があります。

解法：ページ番号の偶奇性と特定の条件をチェックして、操作が有効かどうかを判断します。

#include <iostream>

using namespace std;

typedef long long ll;

void validatePageTurn() {
    int currentPage, targetSum;
    cin >> currentPage >> targetSum;
    
    bool isValid = true;
    if (targetSum != 0) {
        if (targetSum % 2 == 0) {
            isValid = false;
        } else if (((targetSum - 1) / 2) % 2 != currentPage % 2) {
            isValid = false;
        }
    }
    
    cout << (isValid ? "YES" : "NO") << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int testCases;
    cin >> testCases;
    while (testCases--) {
        validatePageTurn();
    }
    
    return 0;
}

問題L：文字列変換の検証

この問題では、文字列が特定のパターンに変換可能かどうかを判断する必要があります。

解法：まずパターンとの一致を確認し、残りの文字が条件を満たすかどうかを検証します。

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

using namespace std;

typedef long long ll;

void checkTransformation() {
    int length;
    cin >> length;
    
    string input;
    cin >> input;
    
    string pattern = "CHICKEN";
    int matchIndex = 0;
    
    vector<int> charCount(26, 0);
    for (char character : input) {
        if (matchIndex < pattern.size() && character == pattern[matchIndex]) {
            matchIndex++;
        } else {
            charCount[character - 'A']++;
        }
    }
    
    if (matchIndex == pattern.size()) {
        int maxFrequency = *max_element(charCount.begin(), charCount.end());
        int extraChars = length - pattern.size();
        
        if (extraChars % 2 == 0 && maxFrequency <= extraChars / 2) {
            cout << "YES\n";
            return;
        }
    }
    
    cout << "NO\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int testCases;
    cin >> testCases;
    while (testCases--) {
        checkTransformation();
    }
    
    return 0;
}