A. 二分探索の学習

基本的な二分探索アルゴリズムを実装する問題です。指定された範囲内でターゲット値を見つけるために必要なステップ数を計算します。

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

using namespace std;

int binary_search_steps(int left, int right, int target) {
    int steps = 0;
    while (left <= right) {
        steps++;
        int mid = left + (right - left) / 2;
        if (mid == target) break;
        if (mid < target) left = mid + 1;
        else right = mid - 1;
    }
    return steps;
}

void solve() {
    int left_bound, right_bound, target_val;
    cin >> left_bound >> right_bound >> target_val;
    cout << binary_search_steps(left_bound, right_bound, target_val) << endl;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int test_cases;
    cin >> test_cases;
    while (test_cases--) {
        solve();
    }
    return 0;
}

B. チェッカーパターンの数え上げ

動的計画法を使用して、n列の場合のパターン総数を計算します。nが偶数の場合と奇数場合で計算式が異なり、結果をmodで処理する必要があります。

#include <iostream>
#include <vector>

using namespace std;

const long long MOD = 1e9 + 7;
const int MAX = 1e6 + 10;

vector<long long> pattern_count(MAX);

void initialize() {
    pattern_count[1] = 1;
    for (int i = 2; i < MAX; i++) {
        if (i % 2 == 1) {
            pattern_count[i] = (2 * pattern_count[i - 1] % MOD - 1) % MOD;
        } else {
            pattern_count[i] = (2 * pattern_count[i - 1] % MOD + 1) % MOD;
        }
    }
}

void solve() {
    int columns;
    cin >> columns;
    cout << (pattern_count[columns] + MOD) % MOD << endl;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    initialize();
    
    int test_cases;
    cin >> test_cases;
    while (test_cases--) {
        solve();
    }
    return 0;
}

C. 文字列の変換

文字列sを走査し、各文字を結果の文字列の先頭文字と比較して、辞書順で小さい方を前に配置する問題です。

#include <iostream>
#include <deque>
#include <string>

using namespace std;

void solve() {
    string input_str;
    cin >> input_str;
    
    deque<char> result_deque;
    for (char current_char : input_str) {
        if (result_deque.empty()) {
            result_deque.push_back(current_char);
        } else {
            if (current_char <= result_deque.front()) {
                result_deque.push_front(current_char);
            } else {
                result_deque.push_back(current_char);
            }
        }
    }
    
    for (char c : result_deque) {
        cout << c;
    }
    cout << endl;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int test_cases;
    cin >> test_cases;
    while (test_cases--) {
        solve();
    }
    return 0;
}

G. 行列の部分和チェック

二次元の累積和（プレフィックスサム）を使用して、与えられたx×y行列が元の行列内で条件を満たすかを判定します。

#include <iostream>
#include <vector>

using namespace std;

const int MAX_SIZE = 2010;

void solve() {
    int rows, cols, sub_rows, sub_cols;
    cin >> rows >> cols >> sub_rows >> sub_cols;
    
    vector<vector<int>> matrix(rows + 1, vector<int>(cols + 1, 0));
    vector<vector<long long>> prefix_sum(rows + 1, vector<long long>(cols + 1, 0));
    
    for (int i = 1; i <= rows; i++) {
        for (int j = 1; j <= cols; j++) {
            cin >> matrix[i][j];
            prefix_sum[i][j] = prefix_sum[i-1][j] + prefix_sum[i][j-1] - prefix_sum[i-1][j-1] + matrix[i][j];
        }
    }
    
    if (prefix_sum[rows][cols] <= 0) {
        cout << "NO" << endl;
        return;
    }
    
    for (int i = 1; i <= rows - sub_rows + 1; i++) {
        for (int j = 1; j <= cols - sub_cols + 1; j++) {
            int end_i = i + sub_rows - 1;
            int end_j = j + sub_cols - 1;
            
            long long submatrix_sum = prefix_sum[end_i][end_j] 
                                    - prefix_sum[i-1][end_j] 
                                    - prefix_sum[end_i][j-1] 
                                    + prefix_sum[i-1][j-1];
            
            if (submatrix_sum >= 0) {
                cout << "NO" << endl;
                return;
            }
        }
    }
    
    cout << "YES" << endl;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int test_cases;
    cin >> test_cases;
    while (test_cases--) {
        solve();
    }
    return 0;
}

H. 関数の特定

入力値nに基づいて、特定の関数を特定する問題です。nが0の場合は1ステップ、それ以外の場合は2ステップで解決できます。

#include <iostream>

using namespace std;

void solve() {
    long long input_val;
    cin >> input_val;
    
    if (input_val == 0) {
        cout << 1 << endl;
    } else {
        cout << 2 << endl;
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int test_cases;
    cin >> test_cases;
    while (test_cases--) {
        solve();
    }
    return 0;
}

J. 並列括弧の検証

括弧の文字列が特定のルールに従っているかを検証する問題です。各括弧ペア内に最大2つの並列括弧のみが許可されます。

#include <iostream>
#include <string>
#include <vector>
#include <stack>

using namespace std;

void solve() {
    string bracket_str;
    cin >> bracket_str;
    
    bool is_valid = true;
    vector<int> nested_count(bracket_str.size(), 0);
    stack<int> bracket_stack;
    
    for (int i = 0; i < bracket_str.size(); i++) {
        if (bracket_str[i] == '(') {
            bracket_stack.push(i);
        } else if (bracket_stack.empty()) {
            is_valid = false;
            break;
        } else {
            bracket_stack.pop();
            if (!bracket_stack.empty()) {
                nested_count[bracket_stack.top()]++;
            }
        }
        
        if (bracket_stack.empty() && i < bracket_str.size() - 1) {
            is_valid = false;
            break;
        }
    }
    
    for (int count : nested_count) {
        if (count > 2) {
            is_valid = false;
            break;
        }
    }
    
    if (!is_valid || !bracket_stack.empty()) {
        cout << "NO" << endl;
    } else {
        cout << "YES" << endl;
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int test_cases;
    cin >> test_cases;
    while (test_cases--) {
        solve();
    }
    return 0;
}