A. カエルのジャンプ

問題の条件に従って直接シミュレーションを行います。データ範囲に注意し、long long型を使用します。

void solve(){
    long long a, b, k;
    cin >> a >> b >> k;
    cout << (k + 1) / 2 * a - k / 2 * b << endl;
}

B. 悩める人々

貪欲法を用いて解決します。パターン「1 0 1」が見つかった場合、最後の1を0に変更することが最適です。

void solve(){
    int n;
    cin >> n;
    vector<int> arr(n);
    for(int i = 0; i < n; i++) cin >> arr[i];
    
    int result = 0;
    for(int i = 0; i < n - 2; i++){
        if(arr[i] == 1 && arr[i+1] == 0 && arr[i+2] == 1){
            result++;
            arr[i+2] = 0;
        }
    }
    cout << result << endl;
}

C. 良い配列

問題の定義に従って配列を検査します。削除された要素が残りの合計の半分に等しい場合の特殊処理に注意します。

void solve(){
    int n;
    cin >> n;
    vector<long long> nums(n);
    unordered_map<long long, int> freq;
    long long total = 0;
    
    for(int i = 0; i < n; i++){
        cin >> nums[i];
        freq[nums[i]]++;
        total += nums[i];
    }
    
    vector<int> indices;
    for(int i = 0; i < n; i++){
        long long rem = total - nums[i];
        if(rem % 2 != 0) continue;
        long long half = rem / 2;
        if(freq.count(half)){
            if(nums[i] == half){
                if(freq[half] >= 2) indices.push_back(i+1);
            } else {
                indices.push_back(i+1);
            }
        }
    }
    
    cout << indices.size() << endl;
    for(int idx : indices) cout << idx << " ";
    cout << endl;
}

D. 切り出し

二分探索を用いて最大の出現回数を求めます。各数値の出現回数を記録し、条件を満たすかチェックします。

bool validate(int x, int m, const unordered_map& counts){
    int cnt = 0;
    for(const auto& entry : counts){
        cnt += entry.second / x;
    }
    return cnt >= m;
}

void solve(){
    int n, m;
    cin >> n >> m;
    unordered_map counts;
    for(int i = 0; i < n; i++){
        int val;
        cin >> val;
        counts[val]++;
    }
    
    int left = 1, right = n;
    while(left < right){
        int mid = (left + right + 1) / 2;
        if(validate(mid, m, counts)){
            left = mid;
        } else {
            right = mid - 1;
        }
    }
    
    vector<int> output;
    for(const auto& entry : counts){
        int times = entry.second / left;
        for(int i = 0; i < times; i++){
            output.push_back(entry.first);
        }
    }
    for(int i = 0; i < m; i++){
        cout << output[i] << " ";
    }
    cout << endl;
}

E. テーマ別コンテスト

数値の出現頻度に基づいて最大スコアを計算します。指数関数的な増加を考慮し、効率的に計算します。

void solve(){
    int n;
    cin >> n;
    unordered_map freq;
    int max_freq = 0;
    for(int i = 0; i < n; i++){
        int x;
        cin >> x;
        freq[x]++;
        max_freq = max(max_freq, freq[x]);
    }
    
    vector<int> frequencies;
    for(const auto& entry : freq){
        frequencies.push_back(entry.second);
    }
    sort(frequencies.begin(), frequencies.end());
    
    int best = 1;
    for(int start = 1; start <= max_freq; start++){
        int current = start;
        int total = 0;
        for(int i = frequencies.size() - 1; i >= 0; i--){
            if(frequencies[i] < current) break;
            total += current;
            current *= 2;
        }
        best = max(best, total);
    }
    cout << best << endl;
}

F1. 子猫との写真（簡易版）

動的計画法を用いて最適解を求めます。状態定義と遷移条件に注意します。

void solve(){
    int n, k, m;
    cin >> n >> k >> m;
    vector<int> values(n);
    for(int i = 0; i < n; i++) cin >> values[i];
    
    vector dp(m+1, vector<long long>(n+1, -1e18));
    dp[0][0] = 0;
    
    for(int selected = 1; selected <= m; selected++){
        for(int pos = 1; pos <= n; pos++){
            for(int prev = max(0, pos - k); prev < pos; prev++){
                dp[selected][pos] = max(dp[selected][pos], 
                                       dp[selected-1][prev] + values[pos-1]);
            }
        }
    }
    
    long long answer = -1;
    for(int i = n - k + 1; i <= n; i++){
        answer = max(answer, dp[m][i]);
    }
    cout << answer << endl;
}

F2. 子猫との写真（発展版）

動的計画法の効率化のために单调キューを使用します。前の状態からの最適な遷移を保持します。

void solve(){
    int n, k, m;
    cin >> n >> k >> m;
    vector<int> values(n);
    for(int i = 0; i < n; i++) cin >> values[i];
    
    if(n / k > m){
        cout << -1 << endl;
        return;
    }
    
    vector dp(m+1, vector<long long>(n+1, -1e18));
    dp[0][0] = 0;
    
    for(int i = 1; i <= m; i++){
        deque<int> dq;
        dq.push_back(0);
        for(int j = 1; j <= n; j++){
            while(!dq.empty() && j - dq.front() > k){
                dq.pop_front();
            }
            dp[i][j] = dp[i-1][dq.front()] + values[j-1];
            while(!dq.empty() && dp[i-1][j] >= dp[i-1][dq.back()]){
                dq.pop_back();
            }
            dq.push_back(j);
        }
    }
    
    long long result = -1;
    for(int i = n - k + 1; i <= n; i++){
        result = max(result, dp[m][i]);
    }
    cout << result << endl;
}