問題A: 停車可能区間の判定 ある区間内に指定された位置が含まれるかを判定する問題です。xとyの大小関係によって、区間の方向が変わる点に注意が必要です。

コード例

#include <iostream>
#include <algorithm>

int main() {
    int n, x, y, z;
    std::cin >> n >> x >> y >> z;
    
    bool result = false;
    
    if (x <= y) {
        if (z >= x && z <= y) {
            result = true;
        }
    } else {
        if (z <= x && z >= y) {
            result = true;
        }
    }
    
    std::cout << (result ? "Yes" : "No") << std::endl;
    
    return 0;
}

問題B: 文字列の位置マッチング 文字列SとTが与えられ、Tの各文字がSのどこで初めて出現するかを求める問題です。二重ループではなく、ポインタを用いた効率的な探索が必要です。

コード例

#include <iostream>
#include <cstring>

int main() {
    char s[200005], t[200005];
    std::cin >> (s + 1) >> (t + 1);
    
    int n = std::strlen(t + 1);
    int pos_s = 1;
    
    for (int i = 1; i <= n; ++i) {
        while (t[i] != s[pos_s]) {
            ++pos_s;
        }
        std::cout << pos_s << " ";
    }
    
    return 0;
}

問題C: 最大身長の計算 各人の肩の高さと頭の高さが与えられ、連続する人々の肩の高さの合計と最後の人の頭の高さを足した値の最大値を求める問題です。

コード例

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

int main() {
    int n;
    std::cin >> n;
    
    std::vector<int> shoulders(n + 1), heads(n + 1);
    long long total_shoulder = 0;
    
    for (int i = 1; i <= n; ++i) {
        std::cin >> shoulders[i] >> heads[i];
        total_shoulder += shoulders[i];
    }
    
    long long max_height = 0;
    for (int i = 1; i <= n; ++i) {
        long long current_height = total_shoulder - shoulders[i] + heads[i];
        max_height = std::max(max_height, current_height);
    }
    
    std::cout << max_height << std::endl;
    
    return 0;
}

問題D: スライディングウィンドウの最小差 数列が与えられ、連続するk個の要素を選んだときの位置の最大値と最小値の差の最小値を求める問題です。ST表（Sparse Table）を用いて効率的に解きます。

コード例

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

const int MAXN = 200005;
const int LOG = 20;

int log_table[MAXN];

void build_log_table(int n) {
    log_table[1] = 0;
    for (int i = 2; i <= n; ++i) {
        log_table[i] = log_table[i/2] + 1;
    }
}

int main() {
    int n, k;
    std::cin >> n >> k;
    
    std::vector<int> p(n + 1), pos(n + 1);
    for (int i = 1; i <= n; ++i) {
        std::cin >> p[i];
        pos[p[i]] = i;
    }
    
    build_log_table(n);
    
    std::vector<std::vector<int>> max_table(LOG, std::vector<int>(n + 1));
    std::vector<std::vector<int>> min_table(LOG, std::vector<int>(n + 1));
    
    for (int i = 1; i <= n; ++i) {
        max_table[0][i] = pos[i];
        min_table[0][i] = pos[i];
    }
    
    for (int j = 1; j < LOG; ++j) {
        for (int i = 1; i + (1 << j) - 1 <= n; ++i) {
            max_table[j][i] = std::max(max_table[j-1][i], max_table[j-1][i + (1 << (j-1))]);
            min_table[j][i] = std::min(min_table[j-1][i], min_table[j-1][i + (1 << (j-1))]);
        }
    }
    
    int answer = INT_MAX;
    for (int i = 1; i + k - 1 <= n; ++i) {
        int length = k;
        int j = log_table[length];
        int max_pos = std::max(max_table[j][i], max_table[j][i + length - (1 << j)]);
        int min_pos = std::min(min_table[j][i], min_table[j][i + length - (1 << j)]);
        answer = std::min(answer, max_pos - min_pos);
    }
    
    std::cout << answer << std::endl;
    
    return 0;
}