コンテスト参加後の復習と解法の整理を行います。問題AからDまでのアプローチとコードをまとめました。

A. Fibonacciness

5要素の数列における最大の「フィボナッチ度」を求める問題です。数列の長さが5であるため、最大でも度は3となります。各位置で成立するフィボナッチ関係の式を検討します。

具体的には、a₀+a₁ = a₂、a₁+a₂ = a₃、a₂+a₃ = a₄の3つの条件が考えられます。これらを満たすよう、未知の要素を決定するパターンをsetで管理し、残りの自由度を求めます。

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int t;
    cin >> t;
    
    while (t--) {
        vector<int> a(4);
        for (int i = 0; i < 4; ++i) cin >> a[i];
        
        unordered_set<int> candidates;
        candidates.insert(a[0] + a[1]);
        candidates.insert(a[2] - a[1]);
        candidates.insert(a[3] - a[2]);
        
        cout << 4 - candidates.size() << '\n';
    }
    
    return 0;
}

B. Farmer John's Card Game

各プレイヤーのカードセットが与えられ、全プレイヤーが順番にカードを出し合うゲームにおいて、カードの値が昇順になるような初期配置を求める問題です。

解法では、各プレイヤーのカードをソートした後、最小カードでプレイヤーを並べ替えます。その後、全てのカードを順に確認して昇順条件が満たされているかを検証します。

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

void solve() {
    int n, m;
    cin >> n >> m;
    
    vector<vector<ll>> cards(n, vector<ll>(m));
    vector<pair<ll, int>> minCard;
    
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            cin >> cards[i][j];
        }
        sort(cards[i].begin(), cards[i].end());
        minCard.emplace_back(cards[i][0], i);
    }
    
    sort(minCard.begin(), minCard.end());
    
    vector<int> order;
    for (auto& p : minCard) order.push_back(p.second);
    
    ll last = -1;
    bool valid = true;
    
    for (int col = 0; col < m && valid; ++col) {
        for (int row = 0; row < n && valid; ++row) {
            int player = order[row];
            if (cards[player][col] <= last) {
                valid = false;
            } else {
                last = cards[player][col];
            }
        }
    }
    
    if (!valid) {
        cout << -1 << '\n';
    } else {
        for (int i = 0; i < n; ++i) {
            cout << order[i] + 1 << " \n"[i == n - 1];
        }
    }
}

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

C. Game of Mathletes

数列から2つの数をペアにし、その和がkとなるペアの最大数を求める問題です。出現頻度をハッシュマップで管理し、全ての候補ペアを効率的に探索します。

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int t;
    cin >> t;
    
    while (t--) {
        int n, k;
        cin >> n >> k;
        
        vector<int> a(n);
        unordered_map<int, int> freq;
        
        for (int i = 0; i < n; ++i) {
            cin >> a[i];
            freq[a[i]]++;
        }
        
        int pairs = 0;
        for (int i = 1; i <= k / 2; ++i) {
            if (k % 2 == 0 && i == k / 2) {
                pairs += freq[i] / 2;
            } else {
                pairs += min(freq[i], freq[k - i]);
            }
        }
        
        cout << pairs << '\n';
    }
    
    return 0;
}

D. Subtract Min Sort

隣接する2要素から最小値を同時に引く操作を繰り返し、最終的に非減少列にできるかを判定する問題です。左から順に操作を適用し、条件を満たさなくなるケースを検出します。

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int t;
    cin >> t;
    
    while (t--) {
        int n;
        cin >> n;
        
        vector<int> a(n);
        for (int i = 0; i < n; ++i) cin >> a[i];
        
        bool possible = true;
        
        for (int i = 1; i < n; ++i) {
            if (a[i - 1] > a[i]) {
                possible = false;
                break;
            }
            int sub = min(a[i - 1], a[i]);
            a[i - 1] -= sub;
            a[i] -= sub;
        }
        
        cout << (possible ? "YES" : "NO") << '\n';
    }
    
    return 0;
}