問題 A: Plus or Minus

問題概要

3つの整数 a, b, c が与えられます。演算子として + または - のいずれかを用いて a と b を結合した結果が c と一致する場合、該当する演算子を出力してください。必ずいずれか一方のみが成立することが保証されています。

解法のアプローチ

単純な条件分岐で対応可能です。和 a + b が c と等しければ + を、等号が成立しなければ必然的に差 a - b が c と一致するため - を出力します。テストケース数に応じてループ処理を適用します。

実装コード

#include <iostream>

void process_case() {
    int val_a, val_b, target;
    std::cin >> val_a >> val_b >> target;
    
    if (val_a + val_b == target) {
        std::cout << "+\n";
    } else {
        std::cout << "-\n";
    }
}

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

---

問題 B: Grab the Candies

問題概要

n 個の袋があり、それぞれ a_i 個のキャンディが入っています。偶数個の袋は先手が、奇数個の袋は後手が獲得します。袋の順序を任意に並び替えたとき、任意の段階で先手の獲得数が後手を厳密に上回る配置が存在するか判定してください。

解法のアプローチ

先手が常に優位に立つためには、偶数袋を全て先頭に配置するのが最適です。この並び替えにより、後手の獲得数は途中まで0で推移し、最終的に奇数袋の総和に達します。したがって、偶数の総和が奇数の総和を厳密に超えるかどうかをチェックするだけで十分です。

実装コード

#include <iostream>
#include <vector>

void solve() {
    int n;
    std::cin >> n;
    long long even_total = 0, odd_total = 0;
    for (int i = 0; i < n; ++i) {
        int candies;
        std::cin >> candies;
        if (candies % 2 == 0) {
            even_total += candies;
        } else {
            odd_total += candies;
        }
    }
    std::cout << (even_total > odd_total ? "YES" : "NO") << "\n";
}

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

---

問題 C: Find and Replace

問題概要

長さ n の文字列 s が与えられます。各アルファベットを 0 または 1 に一対一でマッピングしたとき、結果が 010101... のように交互に並ぶ文字列になるか判定してください。

解法のアプローチ

交互配置が成立するためには、同一文字が出現するインデックス間の距離が常に偶数でなければなりません。各文字の前回出現位置を記録し、現れたインデックスとの差が奇数であれば条件を満たさないため NO を出力します。全体を通過すれば YES です。

実装コード

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

void check_alternating() {
    int len;
    std::cin >> len;
    std::string text;
    std::cin >> text;
    
    std::vector<int> last_pos(26, -1);
    bool possible = true;
    
    for (int idx = 0; idx < len; ++idx) {
        int char_idx = text[idx] - 'a';
        if (last_pos[char_idx] != -1) {
            if ((idx - last_pos[char_idx]) % 2 != 0) {
                possible = false;
                break;
            }
        }
        last_pos[char_idx] = idx;
    }
    std::cout << (possible ? "YES" : "NO") << "\n";
}

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

---

問題 D: Odd Queries

問題概要

長さ n の配列 a に対して q 回のクエリが与えられます。各クエリは区間 [l, r] と値 k で構成され、該当区間の要素を全て k に書き換えた後の配列全体和が奇数になるか判定します。クエリは独立して元の配列を基準に処理されます。

解法のアプローチ

区間書き換え後の総和は、元の総和から区間和を除去し、(r - l + 1) * k を加えることで計算できます。前計算で累積和配列を作成しておけば、各クエリは O(1) で応答可能です。結果の偶奇のみを確認します。

実装コード

#include <iostream>
#include <vector>

void process_queries() {
    int n, q;
    std::cin >> n >> q;
    std::vector<long long> pref(n + 1, 0);
    for (int i = 1; i <= n; ++i) {
        int val;
        std::cin >> val;
        pref[i] = pref[i - 1] + val;
    }
    
    for (int k = 0; k < q; ++k) {
        int l, r, replace_val;
        std::cin >> l >> r >> replace_val;
        long long original_sum = pref[n];
        long long range_sum = pref[r] - pref[l - 1];
        long long modified_total = original_sum - range_sum + 1LL * replace_val * (r - l + 1);
        std::cout << (modified_total % 2 != 0 ? "YES" : "NO") << "\n";
    }
}

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

---

問題 E: Interview

問題概要

n 個の山があり、n-1 個は重さ1の石のみ、1つだけ重さ2の石を1つ含む山があります。30回以内のクエリで重さ2の石を含む山のインデックスを特定する対話型問題です。クエリは山のインデックス群を指定し、その総重量を返します。

解法のアプローチ

二分探索アルゴリズムを適用します。探索範囲を半分に分割し、前半分の期待重量（石の総数）と実際のクエリ結果を比較します。不一致であれば異常値は前半に、一致すれば後半に存在します。これを範囲が1つに絞まるまで繰り返します。出力後は必ずバッファをフラッシュしてください。

実装コード

#include <iostream>
#include <vector>

void interactive_solve() {
    int n;
    std::cin >> n;
    std::vector<int> stone_counts(n + 1);
    std::vector<int> prefix_cnt(n + 1, 0);
    for (int i = 1; i <= n; ++i) {
        std::cin >> stone_counts[i];
        prefix_cnt[i] = prefix_cnt[i - 1] + stone_counts[i];
    }
    
    int left = 1, right = n;
    while (left < right) {
        int mid = left + (right - left) / 2;
        std::cout << "? " << mid - left + 1;
        for (int i = left; i <= mid; ++i) {
            std::cout << " " << i;
        }
        std::cout << "\n" << std::flush;
        
        int actual_weight;
        std::cin >> actual_weight;
        int expected_weight = prefix_cnt[mid] - prefix_cnt[left - 1];
        
        if (actual_weight > expected_weight) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    std::cout << "! " << left << "\n" << std::flush;
}

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

---

問題 F: Bouncy Ball

問題概要

n × m の矩形領域内でボールが移動します。初期位置と進行方向（UL, UR, DL, DR）が与えられ、壁に衝突すると反射します。目標座標に到達するまでの最小反射回数を求めてください。到達不能の場合は -1 を出力します。

解法のアプローチ

状態空間は n × m × 4 通りしかないため、最大でも 4nm ステップ以内に状態がループします。速度ベクトル (dx, dy) を管理し、境界に到達した際に符号を反転させて反射回数をカウントします。シミュレーションステップに上限を設け、到達すれば回数を、超限すれば -1 を出力します。

実装コード

#include <iostream>
#include <string>

void simulate_bounce() {
    int rows, cols, sx, sy, ex, ey;
    std::cin >> rows >> cols >> sx >> sy >> ex >> ey;
    std::string dir_str;
    std::cin >> dir_str;
    
    int vx = (dir_str[0] == 'D') ? 1 : -1;
    int vy = (dir_str[1] == 'L') ? -1 : 1;
    
    int cx = sx, cy = sy;
    int bounce_count = 0;
    int max_steps = 4 * rows * cols;
    
    for (int step = 0; step < max_steps; ++step) {
        if (cx == ex && cy == ey) {
            std::cout << bounce_count << "\n";
            return;
        }
        
        bool hit_wall = false;
        if (vx == 1 && cx == rows) { vx = -1; hit_wall = true; }
        if (vx == -1 && cx == 1) { vx = 1; hit_wall = true; }
        if (vy == 1 && cy == cols) { vy = -1; hit_wall = true; }
        if (vy == -1 && cy == 1) { vy = 1; hit_wall = true; }
        
        if (hit_wall) bounce_count++;
        cx += vx;
        cy += vy;
    }
    std::cout << -1 << "\n";
}

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

---

問題 G1 & G2: Subsequence Addition

問題概要

初期配列 a = [1] から開始します。任意の段階で、既存の要素のサブセット和を計算し、配列の任意の位置に挿入する操作を繰り返せます。目標配列 c をこの操作で再現可能か判定してください。

解法のアプローチ

貪欲法と累積和の概念を利用します。目標配列を昇順にソートしたとき、各要素は「それまでに生成可能な総和以下」でなければなりません。なぜなら、既存の要素の和は現在の総和を超えられないからです。先頭要素が 1 であることを確認し、以降の各要素について c[i] <= current_sum を検証していきます。条件をすべて満たせば構築可能です。

実装コード

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

void check_constructible() {
    int n;
    std::cin >> n;
    std::vector<long long> target(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> target[i];
    }
    std::sort(target.begin(), target.end());
    
    if (target[0] != 1) {
        std::cout << "NO\n";
        return;
    }
    
    long long current_capacity = 1;
    bool possible = true;
    for (int i = 1; i < n; ++i) {
        if (target[i] > current_capacity) {
            possible = false;
            break;
        }
        current_capacity += target[i];
    }
    std::cout << (possible ? "YES" : "NO") << "\n";
}

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