問題A：ヨーグルト購入の最適化（貪欲法）

課題の概要

1本あたりの価格が single 円、2本セットの価格が pair_cost 円のヨーグルトが販売されている。合計 n 本を購入する際、最小の総支出額を求める。

実装アプローチ

セット購入の単価（pair_cost / 2）と通常価格を比較する。セット単価が通常価格より安価な場合は、可能な限りセットで購入し、余った分を単品で処理する。逆の場合は全て単品で購入する方が安くなる。この分岐のみで最適解が得られる。

実装例

#include <iostream>
using namespace std;

void solve_a() {
    int n, single, pair_cost;
    cin >> n >> single >> pair_cost;
    long long total_cost = 0;
    int pair_count = n / 2;
    int remainder = n % 2;

    if (pair_cost < 2 * single) {
        total_cost = 1LL * pair_count * pair_cost + 1LL * remainder * single;
    } else {
        total_cost = 1LL * n * single;
    }
    cout << total_cost << "\n";
}

int main() {
    int test_cases;
    cin >> test_cases;
    while (test_cases--) solve_a();
    return 0;
}

問題B：前進行列の検証（全探索と頻度比較）

課題の概要

パラメータ n, c, d が与えられ、a[i+1][j] = a[i][j] + c および a[i][j+1] = a[i][j] + d を満たす n×n 行列を構成する。入力として n^2 個の整数が渡されるため、これらが正当な行列の要素集合と一致するか判定する。

実装アプローチ

入力配列の最小値を行列の左上要素 base と仮定する。この仮定から、行列内の各座標に対応する期待値を算出し、その出現頻度を入力データと比較する。ハッシュマップを用いてカウントを管理し、全ての期待値が正確に存在すれば「YES」、欠落または過剰があれば「NO」を出力する。

実装例

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;
using ll = long long;

void solve_b() {
    int n; ll c, d;
    cin >> n >> c >> d;
    map<ll, int> freq;
    vector<ll> input_vals(n * n);
    for (int i = 0; i < n * n; ++i) {
        cin >> input_vals[i];
        freq[input_vals[i]]++;
    }
    sort(input_vals.begin(), input_vals.end());
    ll base = input_vals[0];
    bool valid = true;

    for (int i = 0; i < n && valid; ++i) {
        for (int j = 0; j < n; ++j) {
            ll target = base + 1LL * i * c + 1LL * j * d;
            if (freq[target] <= 0) {
                valid = false;
                break;
            }
            freq[target]--;
        }
    }
    cout << (valid ? "YES" : "NO") << "\n";
}

int main() {
    int t; cin >> t;
    while (t--) solve_b();
    return 0;
}

問題C：深海の攻撃シミュレーション（両端ポインタ）

課題の概要

耐久度配列 hp を持つ n 隻の艦隊がある。総攻撃回数 k が与えられ、交互に左端と右端の艦を攻撃する。耐久度が0になると艦は除外され、攻撃対象がシフトする。撃沈数の合計を求める。

実装アプローチ

攻撃回数を左側担当分 left_atk と右側担当分 right_atk に分割する。両端にポインタを配置し、現在の艦の耐久度と割り当てられた攻撃回数を比較しながら消費する。攻撃余力が艦の耐久を上回る場合は撃沈カウントを増やしポインタを内側に移動させ、下回る場合は艦の耐久を減少させてその側の処理を終了する。

実装例

#include <iostream>
#include <vector>
using namespace std;
using ll = long long;

void solve_c() {
    int n; ll k;
    cin >> n >> k;
    vector<ll> hp(n + 1);
    for (int i = 1; i <= n; ++i) cin >> hp[i];

    ll left_atk = (k + 1) / 2;
    ll right_atk = k / 2;
    ll sunk_count = 0;
    int l = 1, r = n;

    while (l <= r && (left_atk > 0 || right_atk > 0)) {
        if (left_atk > 0) {
            if (left_atk >= hp[l]) {
                left_atk -= hp[l];
                sunk_count++;
                l++;
            } else {
                hp[l] -= left_atk;
                left_atk = 0;
            }
        }
        if (right_atk > 0 && l <= r) {
            if (hp[r] > 0) {
                if (right_atk >= hp[r]) {
                    right_atk -= hp[r];
                    sunk_count++;
                    r--;
                } else {
                    hp[r] -= right_atk;
                    right_atk = 0;
                }
            } else {
                r--;
            }
        }
    }
    cout << sunk_count << "\n";
}

int main() {
    int t; cin >> t;
    while (t--) solve_c();
    return 0;
}

問題D：不完全な部分列探索（スライディングウィンドウ）

課題の概要

長さ n の配列 A と長さ m の配列 B が与えられる。A の連続部分列（長さ m）について、並び替え後に B と一致する要素数が k 以上となる区間数を数える。

実装アプローチ

スライディングウィンドウを用いて A 上で区間を移動させる。ウィンドウ内の各数値の出現頻度とターゲット配列 B の頻度を比較し、一致する要素の総数を動的に管理する。区間が1マス移動する際、退出要素の一致判定を解除し、進入要素の一致判定を追加する処理のみを行うことで、時間計算量を O(n) に抑える。

実装例

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

void solve_d() {
    int n, m, k;
    cin >> n >> m >> k;
    vector<int> A(n);
    for (int &x : A) cin >> x;

    unordered_map<int, int> target_freq;
    for (int i = 0; i < m; ++i) {
        int val; cin >> val;
        target_freq[val]++;
    }

    unordered_map<int, int> window_freq;
    int match_cnt = 0;
    int valid_windows = 0;

    for (int r = 0; r < n; ++r) {
        int entering = A[r];
        window_freq[entering]++;
        if (window_freq[entering] <= target_freq[entering]) {
            match_cnt++;
        }

        if (r >= m - 1) {
            if (match_cnt >= k) valid_windows++;
            int leaving = A[r - m + 1];
            if (window_freq[leaving] <= target_freq[leaving]) {
                match_cnt--;
            }
            window_freq[leaving]--;
        }
    }
    cout << valid_windows << "\n";
}

int main() {
    int t; cin >> t;
    while (t--) solve_d();
    return 0;
}

問題E：最長反転区間の決定（差分配列）

課題の概要

バイナリ文字列 s が与えられ、任意の連続する k 文字を反転させる操作が可能である。文字列全体を全て '1' にできる最大の k を求める。

実装アプローチ

k を n から降順に検証する。各 k に対して、差分配列を用いて反転操作の影響範囲を管理する。左端から順に走査し、現在の文字が '0' の場合、反転操作を適用し差分配列を更新する。末尾まで整合性が保たれればその k が最大値となる。

実装例

#include <iostream>
#include <string>
#include <vector>
using namespace std;

void solve_e() {
    int n; string s;
    cin >> n >> s;
    vector<int> state(n);
    for (int i = 0; i < n; ++i) state[i] = s[i] - '0';

    for (int k = n; k >= 1; --k) {
        vector<int> diff(n + 1, 0);
        int current_flip = 0;
        bool possible = true;
        for (int i = 0; i <= n - k; ++i) {
            current_flip += diff[i];
            int actual = (state[i] + current_flip) % 2;
            if (actual == 0) {
                current_flip++;
                diff[i]++;
                diff[i + k]--;
            }
        }
        for (int i = max(0, n - k + 1); i < n; ++i) {
            current_flip += diff[i];
            if ((state[i] + current_flip) % 2 == 0) {
                possible = false;
                break;
            }
        }
        if (possible) {
            cout << k << "\n";
            return;
        }
    }
}

int main() {
    int t; cin >> t;
    while (t--) solve_e();
    return 0;
}

問題F：非対称ゲームの勝利数最大化（XOR演算と組み合わせ最適化）

課題の概要

1, 2, 3, 4 の出現回数が与えられる。配列のXOR和が0のときBobが勝利する。数値を最適な順序で除去していった場合、Bobが勝利する最大回数を求める。

実装アプローチ

数値4はXOR和に影響しないため、ペア単位で独立してカウント可能である。1, 2, 3 については、各数値の偶数ペアを利用する戦略と、1・2・3を相互に相殺する戦略の2通りを比較する。両戦略から得られる勝利数を算出し、特殊な奇数パターンが発生した場合は補正項を加えた上で最大値を出力する。

実装例

#include <iostream>
#include <algorithm>
using namespace std;
using ll = long long;

void solve_f() {
    ll cnt1, cnt2, cnt3, cnt4;
    cin >> cnt1 >> cnt2 >> cnt3 >> cnt4;

    ll strat_pair_cancel = min({cnt1, cnt2, cnt3}) + cnt4 / 2;

    ll base_even_pairs = cnt1 / 2 + cnt2 / 2 + cnt3 / 2 + cnt4 / 2;
    bool all_odd = (cnt1 % 2 == 1 && cnt2 % 2 == 1 && cnt3 % 2 == 1);
    bool equal_odd = (cnt1 == cnt2 && cnt2 == cnt3 && cnt1 % 2 == 1);
    ll bonus = (all_odd || equal_odd) ? 1 : 0;
    ll strat_individual = base_even_pairs + bonus;

    cout << max(strat_pair_cancel, strat_individual) << "\n";
}

int main() {
    int t; cin >> t;
    while (t--) solve_f();
    return 0;
}