問題2824: 目標値より小さい和を持つインデックスペアの数え上げ

この問題は、全ての可能なペアを列挙して条件を満たすものをカウントするだけで解決できます。

class Solution {
public:
    int countPairs(vector<int>& values, int target) {
        int length = values.size();
        int result = 0;
        for(int i = 0; i + 1 < length; i++) {
            for(int j = i + 1; j < length; j++) {
                if(values[i] + values[j] < target)
                    result++;
            }
        }
        return result;
    }
};

問題2825: 循環増加による文字列の部分列変換

この問題は、二つのポインタを使って文字列を一度走査するだけで解決できます。

class Solution {
public:
    bool canMakeSubsequence(string source, string target) {
        int matchCount = 0;
        for (int i = 0; i < source.size(); i++) {
            if (source[i] == target[matchCount]) {
                matchCount++;
            } else if (source[i] + 1 == target[matchCount] || (source[i] == 'z' && target[matchCount] == 'a')) {
                matchCount++;
            }
        }
        return matchCount == target.size();
    }
};

問題2826: 三つのグループのソート

この問題は動的計画法（DP）で効率的に解くことができます。DP[i][j]は、i番目の数までを処理し、i番目の数をjに変更した場合の最小操作回数を表します。

class Solution {
public:
    int minimumOperations(vector<int>& arr) {
        int n = arr.size();
        vector<vector<int>> dp(n, vector<int>(4, 0));
        dp[0][1] = arr[0] != 1;
        dp[0][2] = arr[0] != 2;
        dp[0][3] = arr[0] != 3;
        for(int i = 1; i < n; i++) {
            dp[i][1] = dp[i-1][1] + (arr[i] != 1);
            dp[i][2] = min(dp[i-1][1] + (arr[i] != 2), dp[i-1][2] + (arr[i] != 2));
            dp[i][3] = min({dp[i-1][1], dp[i-1][2], dp[i-1][3]}) + (arr[i] != 3);
        }
        return min({dp[n-1][1], dp[n-1][2], dp[n-1][3]});
    }
};

空間効率を改善するために、一次元配列を使用した最適化も可能です。

class Solution {
public:
    int minimumOperations(vector<int>& arr) {
        int state[4]{0};
        for(auto val : arr)
            for(int i = 3; i > 0; i--)
                state[i] = *min_element(state + 1, state + i + 1) + (i != val);
        
        return *min_element(state + 1, state + 4);
    }
};

問題2827: 指定範囲内の美しい整数の数え上げ

この問題は数位動的計画法（Digit DP）を用いて解くことができます。詳細な解法は後日追加予定です。