最短区間カバー問題

指定された種類数を満たす最小連続区間を探索する問題です。スライディングウィンドウ手法を用い、要素の出現頻度を動的に管理しながら最適解を導出します。

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

int main() {
    int n, m;
    cin >> n >> m;
    vector<int> cookTypes(n);
    for (int i = 0; i < n; ++i) {
        cin >> cookTypes[i];
    }

    vector<int> freq(2001, 0);
    int uniqueCount = 0;
    int minLength = INT_MAX;
    int left = 0, right = 0;
    int startIdx = -1, endIdx = -1;

    while (right < n) {
        if (freq[cookTypes[right]] == 0) {
            uniqueCount++;
        }
        freq[cookTypes[right]]++;
        right++;

        while (uniqueCount == m && left < right) {
            if (right - left < minLength) {
                minLength = right - left;
                startIdx = left;
                endIdx = right - 1;
            }
            freq[cookTypes[left]]--;
            if (freq[cookTypes[left]] == 0) {
                uniqueCount--;
            }
            left++;
        }
    }

    cout << startIdx + 1 << " " << endIdx + 1 << endl;
    return 0;
}

色付き要素のソート判定

RとBの色を持つ要素をソートし、特定の条件を満たすかを検証します。昇順と降順のソート後、各要素の値と色の関係性をチェックすることで解を判定します。

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

struct Element {
    int value;
    char color;
};

bool compareValue(Element a, Element b) {
    if (a.value != b.value) return a.value < b.value;
    return a.color < b.color;
}

int main() {
    int testCases;
    cin >> testCases;
    while (testCases--) {
        int n;
        cin >> n;
        vector<Element> data(n);
        string colorStr;
        for (int i = 0; i < n; ++i) {
            cin >> data[i].value;
        }
        cin >> colorStr;
        for (int i = 0; i < n; ++i) {
            data[i].color = colorStr[i];
        }

        sort(data.begin(), data.end(), compareValue);
        bool isValid = true;
        for (int i = 0; i < n; ++i) {
            if (data[i].value == i + 1) continue;
            if (data[i].value < i + 1 && data[i].color == 'R') continue;
            if (data[i].value > i + 1 && data[i].color == 'B') continue;
            isValid = false;
            break;
        }

        if (isValid) {
            cout << "YES" << endl;
            continue;
        }

        reverse(data.begin(), data.end());
        isValid = true;
        for (int i = 0; i < n; ++i) {
            if (data[i].value == i + 1) continue;
            if (data[i].value < i + 1 && data[i].color == 'R') continue;
            if (data[i].value > i + 1 && data[i].color == 'B') continue;
            isValid = false;
            break;
        }
        cout << (isValid ? "YES" : "NO") << endl;
    }
    return 0;
}

チーム最適化問題

チームの戦力値と要員数の制約下で最大総戦力を求める問題です。要員数で降順ソートし、優先度付きキューを用いて動的に最適なチームを構築します。

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

struct Team {
    long long strength;
    long long requirement;
};

bool compareByRequirement(Team a, Team b) {
    return a.requirement > b.requirement;
}

int main() {
    int n;
    cin >> n;
    vector<Team> teams(n);
    for (int i = 0; i < n; ++i) {
        cin >> teams[i].strength >> teams[i].requirement;
    }

    sort(teams.begin(), teams.end(), compareByRequirement);
    priority_queue<Team, vector<Team>, greater<Team>> minHeap;
    long long totalStrength = 0;
    long long maxTotal = 0;

    for (int i = 0; i < n; ++i) {
        minHeap.push(teams[i]);
        totalStrength += teams[i].strength;
        while (minHeap.size() > teams[i].requirement) {
            totalStrength -= minHeap.top().strength;
            minHeap.pop();
        }
        maxTotal = max(maxTotal, totalStrength);
    }

    cout << maxTotal << endl;
    return 0;
}

電子配置構造生成

原子の電子配置を再帰的に構築する問題です。各能層の電子数を計算し、能層順に整理して出力します。座標変換と再帰呼び出しを用いて効率的に構造を生成します。

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

char orbitalSymbols[] = {'#', 's', 'p', 'd', 'f'};
int maxElectrons[] = {0, 2, 6, 10, 14};
int electronCounts[10][5] = {0};

void buildElectronConfig(int remaining, int level, int sublevel) {
    electronCounts[level][sublevel] = min(maxElectrons[sublevel], remaining);
    int nextRemaining = remaining - maxElectrons[sublevel];
    if (nextRemaining <= 0) return;

    if (sublevel == 1) {
        sublevel = level / 2 + 1;
        level = (level + 1) / 2 + 1;
    } else {
        level++;
        sublevel--;
    }
    buildElectronConfig(nextRemaining, level, sublevel);
}

int main() {
    int totalElectrons;
    cin >> totalElectrons;
    buildElectronConfig(totalElectrons, 1, 1);

    for (int level = 1; ; level++) {
        bool hasElectrons = false;
        for (int sublevel = 1; sublevel <= 4; sublevel++) {
            if (electronCounts[level][sublevel] > 0) {
                cout << level << orbitalSymbols[sublevel] << electronCounts[level][sublevel] << " ";
                hasElectrons = true;
            }
        }
        if (!hasElectrons) return 0;
        cout << endl;
    }
    return 0;
}

ビット演算による最小OR値計算

複数区間のXOR和のOR最小値を求める問題です。高位から低位へ処理し、前缀XORと分割点の可能性を動的に管理することで効率的に解を求めます。

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

int main() {
    long long n, m;
    cin >> n >> m;
    vector<long long> prefixXor(n + 1, 0);
    for (int i = 1; i <= n; ++i) {
        cin >> prefixXor[i];
        prefixXor[i] ^= prefixXor[i - 1];
    }

    vector<bool> validSplit(n + 1, true);
    long long result = 0;

    for (int bit = 62; bit >= 0; --bit) {
        long long countValid = 0;
        for (int i = 1; i <= n; ++i) {
            if (validSplit[i] && !(prefixXor[i] & (1LL << bit))) {
                countValid++;
            }
        }

        if (countValid >= m && !(prefixXor[n] & (1LL << bit))) {
            for (int i = 1; i <= n; ++i) {
                if (prefixXor[i] & (1LL << bit)) {
                    validSplit[i] = false;
                }
            }
        } else {
            result |= (1LL << bit);
        }
    }

    cout << result << endl;
    return 0;
}

タスク割り当て最適化

タスクを複数の工作者に割り当てる際の最短総時間を求めます。二分探索を用いて可能かを判定し、貪欲法で具体的な割り当てを出力します。

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

struct Assignment {
    int start;
    int end;
};

bool canAssign(vector<int>& tasks, int workers, long long maxTime) {
    int currentWorker = 1;
    long long currentLoad = 0;
    for (int task : tasks) {
        if (currentLoad + task > maxTime) {
            currentWorker++;
            currentLoad = task;
            if (currentWorker > workers) return false;
        } else {
            currentLoad += task;
        }
    }
    return true;
}

void printAssignment(vector<int>& tasks, int workers, long long maxTime) {
    vector<Assignment> assignments(workers + 1);
    int currentWorker = workers;
    long long currentLoad = 0;
    for (int i = tasks.size() - 1; i >= 0; --i) {
        if (currentLoad + tasks[i] > maxTime) {
            assignments[currentWorker].end = i + 1;
            currentWorker--;
            currentLoad = tasks[i];
            assignments[currentWorker].start = i + 1;
            assignments[currentWorker].end = i + 1;
        } else {
            currentLoad += tasks[i];
        }
    }
    assignments[1].start = 1;

    for (int i = 1; i <= workers; ++i) {
        if (assignments[i].start == 0) {
            cout << "0 0\n";
        } else {
            cout << assignments[i].start << " " << assignments[i].end << "\n";
        }
    }
}

int main() {
    int tasksCount, workers;
    cin >> tasksCount >> workers;
    vector<int> tasks(tasksCount);
    long long low = 0, high = 0;
    for (int i = 0; i < tasksCount; ++i) {
        cin >> tasks[i];
        low = max(low, (long long)tasks[i]);
        high += tasks[i];
    }

    long long result = high;
    while (low <= high) {
        long long mid = (low + high) / 2;
        if (canAssign(tasks, workers, mid)) {
            result = mid;
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }

    printAssignment(tasks, workers, result);
    return 0;
}