A - 数列の並べ替えとスコア最適化

長さ n の整数列 a が与えられる。初期値が 0 の変数 s に対して、a の要素を順に加算する。s が偶数になった場合、ポイントを 1 加算した上で s を 2 で割った余り（つまり s % 2）に更新する。この操作を繰り返す中で、得られるポイントの合計を最大化するために、a の要素をどのように並び替えるべきか。

重要な観察として、奇数の個数に注目する。すべての要素が偶数であれば、s は常に 0 から始まり、最初の加算で偶数 → ポイント獲得 → s=0 に戻るため、最低でも 1 点を得ることができる。一方、すべてが奇数の場合は、交互に 0,1 を繰り返すため、最大で n−1 点が上限となる。それ以外のケースでは、奇数の個数 + 1 が理論上の最大スコアとなる配置が可能である。

#include <bits/stdc++.h>
using namespace std;

void solve() {
    int n;
    cin >> n;
    int odd_count = 0;
    for (int i = 0; i < n; ++i) {
        int x;
        cin >> x;
        if (x % 2 == 1) odd_count++;
    }
    
    if (odd_count == 0) {
        cout << 1 << '\n';
    } else if (odd_count == n) {
        cout << n - 1 << '\n';
    } else {
        cout << odd_count + 1 << '\n';
    }
}

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

B - 棒を使った等脚台形の構成

n 本の棒があり、それぞれの長さが与えられる。ここから 4 本を選んで等脚台形（長方形や正方形も含む）を作れるか判定せよ。できる場合はその一例を出力し、不可能なら −1 を出力する。

等脚台形の成立条件として、二つの脚の長さが等しく、上底 A、下底 C、脚 B について三角不等式 A+2B>C を満たす必要がある。まず配列をソートし、最も長い脚のペアを探して固定する。残りの棒から上底候補を小さい順に選び、対応する下底を二分探索で探すことで効率的に検証できる。

#include <bits/stdc++.h>
using namespace std;

void solve() {
    int n;
    cin >> n;
    vector<int> sticks(n);
    for (int i = 0; i < n; ++i) {
        cin >> sticks[i];
    }
    sort(sticks.begin(), sticks.end());
    
    // 脚のペアを探す（大きい方から）
    for (int i = n - 1; i > 0; --i) {
        if (sticks[i] != sticks[i-1]) continue;
        int leg = sticks[i];
        
        // 上底候補
        for (int j = 0; j < n; ++j) {
            if (j == i || j == i-1) continue;
            int top = sticks[j];
            
            // 下底候補：top + 2*leg より小さく、かつ他のインデックス
            auto it = lower_bound(sticks.begin(), sticks.end(), top);
            while (it != sticks.end()) {
                int idx = distance(sticks.begin(), it);
                if (idx == i || idx == i-1 || idx == j) {
                    ++it;
                    continue;
                }
                break;
            }
            
            if (it == sticks.end() || *it >= top + 2*leg) continue;
            
            cout << top << " " << leg << " " << leg << " " << *it << '\n';
            return;
        }
    }
    
    cout << -1 << '\n';
}

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

C - 嘘つき者の配置と論理的整合性

n 人の人が一列に並んでおり、各人 i は「自分と自分より左にいる嘘つきは a_i 人いる」と発言している。ただし、嘘つき者は隣接してはいけないという制約がある。このような状況を満たす組み合わせの総数を mod 998244353 で求めよ。

動的計画法を用いる。dp[i][0] を「i 番目が正直者」、dp[i][1] を「i 番目が嘘つき」とするときの有効なパターン数とする。また、cnt[i] には「i 番目が嘘つきだと仮定したときに、[1,i) 区間の嘘つき人数」を記録する。遷移では、a[i] の値が前の状態と整合するかを確認し、隣接しないように遷移を制限する。

#include <bits/stdc++.h>
using namespace std;

const int MOD = 998244353;
const int MAXN = 200005;

long long dp[MAXN][2];
int expected[MAXN];

void solve() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> expected[i];
    }
    
    // 初期状態
    if (expected[1] == 0) {
        dp[1][0] = 1;  // 正直
        dp[1][1] = 1;  // 嘘つき
    } else {
        dp[1][0] = 1;
        dp[1][1] = 0;
    }
    
    for (int i = 2; i <= n; ++i) {
        // i番目が正直の場合
        dp[i][0] = 0;
        if (expected[i] == expected[i-1]) {
            dp[i][0] = (dp[i][0] + dp[i-1][0]) % MOD;
        }
        if (expected[i] == expected[i-1] + 1) {
            dp[i][0] = (dp[i][0] + dp[i-1][1]) % MOD;
        }
        
        // i番目が嘘つきの場合 → 前は正直
        dp[i][1] = dp[i-1][0];
    }
    
    cout << (dp[n][0] + dp[n][1]) % MOD << '\n';
}

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

D - 数字の分割と再構成可能性

長さ n の正整数列 a があり、以下の操作を任意回行える：差の絶対値が 1 以下の二つの数 x,y を選び、削除して x+y を追加する。この結果として、目標の数列 b（長さ m）を得られるか判定せよ。

逆方向の思考が有効。最終的な数列 b の各要素を可能な限り分割していく。偶数は二つの x/2 に、奇数は floor(x/2) と ceil(x/2) に分割される。この分割をシミュレーションし、元の a と一致する多重集合が得られるかを確認する。優先度付きキューを使って大きい数から処理するのが効率的。

#include <bits/stdc++.h>
using namespace std;

void solve() {
    int n, m;
    cin >> n >> m;
    priority_queue<int> src, target;
    long long sum_src = 0, sum_tgt = 0;
    
    for (int i = 0; i < n; ++i) {
        int x;
        cin >> x;
        src.push(x);
        sum_src += x;
    }
    for (int i = 0; i < m; ++i) {
        int x;
        cin >> x;
        target.push(x);
        sum_tgt += x;
    }
    
    if (sum_src != sum_tgt) {
        cout << "NO\n";
        return;
    }
    
    while (!target.empty()) {
        int val = target.top(); target.pop();
        if (src.empty()) {
            cout << "NO\n";
            return;
        }
        
        int top = src.top();
        if (val == top) {
            src.pop();
        } else if (val < top) {
            cout << "NO\n";
            return;
        } else {
            // 分割して戻す
            target.push(val / 2);
            target.push((val + 1) / 2);
        }
    }
    
    cout << "YES\n";
}

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