A: 剰余演算

基本的な剰余演算の問題。入力値に対して特定の計算を行う。

void solve() {
    int n;
    cin >> n;
    int result = (n + 1) / 2;
    cout << result << endl;
}

B: 3の倍数判定

数字列の連結結果が3の倍数かを判定する。各桁の総和が3で割り切れるかどうかで判断可能。

void solve() {
    int count;
    cin >> count;
    int digit_sum = 0;
    for (int i = 0; i < count; i++) {
        string num_str;
        cin >> num_str;
        for (char digit : num_str) {
            digit_sum += digit - '0';
        }
    }
    cout << (digit_sum % 3 == 0 ? "YES" : "NO") << endl;
}

C: 充電最適化

2種類の充電方法を比較し、最速の充電時間を計算する。急速充電の利用可否に応じて分岐処理を行う。

void solve() {
    double current, slow_rate, threshold, fast_rate, normal_rate;
    cin >> current >> slow_rate >> threshold >> fast_rate >> normal_rate;
    double total_time;
    if (current <= threshold) {
        total_time = (100 - current) / fast_rate;
    } else {
        double option1 = (100 - current) / normal_rate;
        double option2 = (current - threshold) / slow_rate + (100 - threshold) / fast_rate;
        total_time = min(option1, option2);
    }
    cout << fixed << setprecision(7) << total_time << endl;
}

D: 文字列と最大公約数

文字列形式の数値と整数の最大公約数を求める。モジュロ演算と再帰的アルゴリズムを組み合わせる。

long long calculate_gcd(long long a, long long b) {
    return b == 0 ? a : calculate_gcd(b, a % b);
}

void solve() {
    string large_num;
    int divisor;
    cin >> large_num >> divisor;
    long long remainder = 0;
    for (char c : large_num) {
        remainder = (remainder * 10 + (c - '0')) % divisor;
    }
    cout << calculate_gcd(divisor, remainder) << endl;
}

E: 行列の最短経路

行列移動時の最小コスト経路を探索する。優先度付きキューを用いたダイクストラ法を適用。

struct GridNode {
    int cost;
    pair position;
    bool operator>(const GridNode& other) const {
        return cost > other.cost;
    }
};

void solve() {
    int size;
    cin >> size;
    vector grid(size + 1, vector<int>(size + 1));
    for (int i = 1; i <= size; i++) {
        for (int j = 1; j <= size; j++) {
            cin >> grid[i][j];
        }
    }

    vector min_cost(size + 1, vector<int>(size + 1, INT_MAX));
    min_cost[1][1] = grid[1][1];
    priority_queue pq;
    pq.push({grid[1][1], {1, 1}});

    const vector> directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    while (!pq.empty()) {
        auto [row, col] = pq.top().position;
        pq.pop();
        for (auto [dr, dc] : directions) {
            int new_row = row + dr;
            int new_col = col + dc;
            if (new_row >= 1 && new_row <= size && new_col >= 1 && new_col <= size) {
                int new_cost = max(min_cost[row][col], grid[new_row][new_col]);
                if (new_cost < min_cost[new_row][new_col]) {
                    min_cost[new_row][new_col] = new_cost;
                    pq.push({new_cost, {new_row, new_col}});
                }
            }
        }
    }
    cout << min_cost[size][size] << endl;
}

F: 区間クエリ処理

配列の部分区間における最大絶対値を効率的に計算。セグメント木で各種統計量を管理。

struct SegmentNode {
    long long total, max_val, min_val;
    long long prefix_max, suffix_max;
    long long prefix_min, suffix_min;
};

class SegmentTree {
    vector<SegmentNode> tree;
    int array_size;

    void merge_nodes(SegmentNode& parent, const SegmentNode& left, const SegmentNode& right) {
        parent.total = left.total + right.total;
        parent.prefix_max = max(left.prefix_max, left.total + right.prefix_max);
        parent.suffix_max = max(right.suffix_max, right.total + left.suffix_max);
        parent.prefix_min = min(left.prefix_min, left.total + right.prefix_min);
        parent.suffix_min = min(right.suffix_min, right.total + left.suffix_min);
        parent.max_val = max({left.max_val, right.max_val, left.suffix_max + right.prefix_max});
        parent.min_val = min({left.min_val, right.min_val, left.suffix_min + right.prefix_min});
    }

public:
    SegmentTree(const vector<int>& data) {
        array_size = data.size();
        tree.resize(4 * array_size);
        build_tree(1, 1, array_size, data);
    }

    void build_tree(int idx, int left, int right, const vector<int>& data) {
        if (left == right) {
            int val = data[left - 1];
            tree[idx] = {val, val, val, val, val, val, val};
            return;
        }
        int mid = (left + right) / 2;
        build_tree(2 * idx, left, mid, data);
        build_tree(2 * idx + 1, mid + 1, right, data);
        merge_nodes(tree[idx], tree[2 * idx], tree[2 * idx + 1]);
    }

    SegmentNode query_range(int idx, int l, int r, int curr_l, int curr_r) {
        if (l <= curr_l && curr_r <= r) {
            return tree[idx];
        }
        int mid = (curr_l + curr_r) / 2;
        if (r <= mid) return query_range(2 * idx, l, r, curr_l, mid);
        if (l > mid) return query_range(2 * idx + 1, l, r, mid + 1, curr_r);
        SegmentNode left_node = query_range(2 * idx, l, r, curr_l, mid);
        SegmentNode right_node = query_range(2 * idx + 1, l, r, mid + 1, curr_r);
        SegmentNode merged;
        merge_nodes(merged, left_node, right_node);
        return merged;
    }
};

void solve() {
    int n;
    cin >> n;
    vector<int> arr(n);
    for (int i = 0; i < n; i++) cin >> arr[i];
    SegmentTree seg_tree(arr);
    int queries;
    cin >> queries;
    while (queries--) {
        int start, end;
        cin >> start >> end;
        SegmentNode res = seg_tree.query_range(1, start, end, 1, n);
        cout << max(res.max_val, abs(res.min_val)) << endl;
    }
}