問題A

問題の指示に従ってシミュレーションを行います。

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

using namespace std;

int main() {
    int size, left, right;
    cin >> size >> left >> right;
    
    vector<int> sequence(size);
    for (int i = 0; i < size; ++i) {
        sequence[i] = i + 1;
    }
    
    reverse(sequence.begin() + left - 1, sequence.begin() + right);
    
    for (int i = 0; i < size; ++i) {
        cout << sequence[i] << (i == size - 1 ? '\n' : ' ');
    }
    
    return 0;
}

問題B

問題の指示に従ってシミュレーションを行います。

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int total, operations;
    cin >> total >> operations;
    
    vector<int> values(operations);
    for (int i = 0; i < operations; ++i) {
        cin >> values[i];
    }
    
    for (int i = 0; i < total; ++i) {
        for (int j = 0; j < operations; ++j) {
            int current;
            cin >> current;
            values[j] -= current;
        }
    }
    
    for (int val : values) {
        if (val > 0) {
            cout << "No" << endl;
            return 0;
        }
    }
    
    cout << "Yes" << endl;
    return 0;
}

問題C

問題文のヒントにより、本物とダミーの鍵の組み合わせは2^N通り存在することがわかります。すべての真偽の組み合わせを列挙するだけで解けます。

#include <iostream>
#include <vector>

using namespace std;

bool validateCombination(int combination, const vector<vector<int>>& tests, 
                       const vector<char>& results, int threshold, int keyCount) {
    vector<bool> keyStatus(keyCount + 1);
    
    for (int i = 0; i < keyCount; ++i) {
        keyStatus[i + 1] = (combination & (1 << i)) != 0;
    }
    
    for (int i = 0; i < tests.size(); ++i) {
        int realCount = 0;
        for (int key : tests[i]) {
            realCount += keyStatus[key];
        }
        
        if (realCount < threshold && results[i] == 'o') return false;
        if (realCount >= threshold && results[i] == 'x') return false;
    }
    
    return true;
}

int main() {
    int keyCount, testCases, threshold;
    cin >> keyCount >> testCases >> threshold;
    
    vector<vector<int>> tests(testCases);
    vector<char> results(testCases);
    
    for (int i = 0; i < testCases; ++i) {
        int testSize;
        cin >> testSize;
        tests[i].resize(testSize);
        for (int j = 0; j < testSize; ++j) {
            cin >> tests[i][j];
        }
        cin >> results[i];
    }
    
    int validCombinations = 0;
    for (int i = 0; i < (1 << keyCount); ++i) {
        if (validateCombination(i, tests, results, threshold, keyCount)) {
            validCombinations++;
        }
    }
    
    cout << validCombinations << endl;
    return 0;
}

問題D

各ビットごとに貢献度を計算します。パターンを観察すると：0001, 0010, 0011, 0100, ... というように、最初に2^i-1個の0があり、その後1と0が2^i個ずつ交互に出現します。これをシミュレーションで解けます。

#include <iostream>

using namespace std;

const int MOD = 998244353;

int main() {
    long long limit, mask;
    cin >> limit >> mask;
    
    long long result = 0;
    
    for (int bit = 0; bit < 60; ++bit) {
        if (!(mask & (1LL << bit))) continue;
        
        long long remaining = max(limit - ((1LL << bit) - 1), 0LL);
        result = (result + (remaining / (1LL << (bit + 1))) * (1LL << bit)) % MOD;
        
        long long remainder = remaining % (1LL << (bit + 1));
        result = (result + min(remainder, 1LL << bit)) % MOD;
    }
    
    cout << result << endl;
    return 0;
}

問題E

古典的な問題です。床関数に注意すると、a_i/a_jの値をw/a_j（w=max a_i）で分割できます。a_jを列挙し、区間ごとに答えを計算します。全体の計算量はsum w/a_iとなり、古典的なw log wの計算量で、w≤10^6です。ただし、a_i=a_jの場合の重複計算に注意が必要です。

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int length;
    cin >> length;
    
    const int MAX_VALUE = 1000000;
    vector<int> numbers(length);
    vector<int> frequency(MAX_VALUE + 1, 0);
    int maximum = 0;
    
    for (int i = 0; i < length; ++i) {
        cin >> numbers[i];
        frequency[numbers[i]]++;
        maximum = max(maximum, numbers[i]);
    }
    
    for (int i = 1; i <= MAX_VALUE; ++i) {
        frequency[i] += frequency[i - 1];
    }
    
    long long result = 0;
    for (int i = 1; i <= maximum; ++i) {
        int count = frequency[i] - frequency[i - 1];
        result -= (long long)count * (count + 1) / 2;
        
        for (int j = 1; j * i <= maximum; ++j) {
            int upper = min(maximum, (j + 1) * i - 1);
            int rangeCount = frequency[upper] - frequency[j * i - 1];
            result += (long long)rangeCount * count * j;
        }
    }
    
    cout << result << endl;
    return 0;
}