ABC 252 問題C

スロットマシンにおいて、各数字が停止する時間を最適化する。各リールの数字位置を記録し、各数字が停止する時間の最大値最小値を求める。

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

using namespace std;

int main() {
    int reel_count;
    cin >> reel_count;
    vector<string> reels(reel_count);
    
    for (int i = 0; i < reel_count; i++) {
        cin >> reels[i];
    }
    
    int min_time = INT_MAX;
    for (int target = 0; target < 10; target++) {
        vector<int> time_slots(10, 0);
        
        for (int i = 0; i < reel_count; i++) {
            for (int position = 0; position < 10; position++) {
                if (reels[i][position] - '0' == target) {
                    time_slots[position]++;
                    break;
                }
            }
        }
        
        int max_time = 0;
        for (int slot = 0; slot < 10; slot++) {
            if (time_slots[slot]) {
                int calc_time = slot + (time_slots[slot] - 1) * 10;
                max_time = max(max_time, calc_time);
            }
        }
        min_time = min(min_time, max_time);
    }
    
    cout << min_time;
    return 0;
}

ABC 252 問題D

整数列から三つ組の選択方法を算出。各数値の出現頻度を使用し、接頭辞・当該値・接尾辞の積和で計算する。

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int element_count;
    cin >> element_count;
    vector<long long> freq_counter(200005, 0);
    
    int number;
    for (int i = 0; i < element_count; i++) {
        cin >> number;
        freq_counter[number]++;
    }
    
    vector<long long> prefix_sums(200005, 0);
    for (int i = 1; i < 200005; i++) {
        prefix_sums[i] = prefix_sums[i - 1] + freq_counter[i - 1];
    }
    
    long long total = 0;
    for (int i = 1; i < 200003; i++) {
        long long current = freq_counter[i];
        long long suffix_total = prefix_sums[200002] - prefix_sums[i];
        total += prefix_sums[i] * current * suffix_total;
    }
    
    cout << total;
    return 0;
}

ABC 253 問題C

クエリ処理によるコレクション操作。挿入、削除、範囲問合せをハッシュマップで処理。

#include <iostream>
#include <unordered_map>
#include <algorithm>

using namespace std;

int main() {
    int query_count;
    scanf("%d", &query_count);
    
    unordered_map<int, int> number_storage;
    int min_val = 1e9, max_val = -1e9;
    
    while (query_count--) {
        int operation;
        scanf("%d", &operation);
        
        if (operation == 1) {
            int value;
            scanf("%d", &value);
            number_storage[value]++;
            min_val = min(min_val, value);
            max_val = max(max_val, value);
        } 
        else if (operation == 2) {
            int value, removal_limit;
            scanf("%d %d", &value, &removal_limit);
            int actual_removed = min(removal_limit, number_storage[value]);
            number_storage[value] -= actual_removed;
            if (number_storage[value] == 0) {
                number_storage.erase(value);
                if (value == min_val || value == max_val) {
                    min_val = (number_storage.empty()) ? 1e9 : min_element(number_storage.begin(), number_storage.end())->first;
                    max_val = (number_storage.empty()) ? -1e9 : max_element(number_storage.begin(), number_storage.end())->first;
                }
            }
        } 
        else {
            printf("%d\n", max_val - min_val);
        }
    }
    return 0;
}

ABC 253 問題D

除算を用いた包含原理の実装。等差数列の集成から排除対象を減算処理。

#include <iostream>

using namespace std;

long long arithmetic_sum(long long first, long long terms) {
    return (terms * (first + (terms * first))) / 2;
}

int main() {
    long long N, A, B;
    cin >> N >> A >> B;
    
    long long total = N * (N + 1) / 2;
    
    long long multiple_A = N / A;
    total -= arithmetic_sum(A, multiple_A);
    
    long long multiple_B = N / B;
    total -= arithmetic_sum(B, multiple_B);
    
    long long lcm = (A * B) / gcd(A, B);
    long long multiple_lcm = N / lcm;
    total += arithmetic_sum(lcm, multiple_lcm);
    
    cout << total;
    return 0;
}

ABC 254 問題C

数列の転置可能性を判定。剰余による再グループ化後、ソート処理で復元。

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

using namespace std;

int main() {
    int len, step;
    cin >> len >> step;
    vector<int> sequence(len);
    
    for (int i = 0; i < len; i++) {
        cin >> sequence[i];
    }
    
    vector<vector<int>> step_groups(step);
    for (int i = 0; i < len; i++) {
        step_groups[i % step].push_back(sequence[i]);
    }
    
    for (auto &group : step_groups) {
        sort(group.begin(), group.end());
    }
    
    vector<int> reconstructed(len);
    for (int i = 0; i < len; i++) {
        reconstructed[i] = step_groups[i % step][i / step];
    }
    
    if (is_sorted(reconstructed.begin(), reconstructed.end())) {
        cout << "Yes";
    } else {
        cout << "No";
    }
    return 0;
}

ABC 254 問題E

グラフの距離制限走査。深さ制約付きBFSで効率的に探索。

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

long long neighbor_sum(vector<vector<int>> &graph, int start, int max_depth) {
    queue<pair<int, int>> traverse_queue;
    vector<bool> visited(graph.size(), false);
    long long total = 0;
    
    traverse_queue.push({start, 0});
    visited[start] = true;
    
    while (!traverse_queue.empty()) {
        auto [node, depth] = traverse_queue.front();
        traverse_queue.pop();
        
        total += node + 1;
        
        if (depth < max_depth) {
            for (int adjacent : graph[node]) {
                if (!visited[adjacent]) {
                    visited[adjacent] = true;
                    traverse_queue.push({adjacent, depth + 1});
                }
            }
        }
    }
    return total;
}

int main() {
    int vertex_count, edge_count;
    cin >> vertex_count >> edge_count;
    vector<vector<int>> graph(vertex_count);
    
    for (int i = 0; i < edge_count; i++) {
        int from, to;
        cin >> from >> to;
        graph[from - 1].push_back(to - 1);
        graph[to - 1].push_back(from - 1);
    }
    
    int query_count;
    cin >> query_count;
    while (query_count--) {
        int query_start, depth_limit;
        cin >> query_start >> depth_limit;
        cout << neighbor_sum(graph, query_start - 1, depth_limit) << "\n";
    }
    return 0;
}