2815. 配列内の最大ペア和

二重ループで全探索する。

class Solution {
public:
    int maxSum(vector<int>& nums) {
        auto getMaxDigit = [](int val) {
            int maxD = 0;
            while (val) {
                if (val % 10 > maxD) maxD = val % 10;
                val /= 10;
            }
            return maxD;
        };
        int n = nums.size();
        int best = -1;
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                if (getMaxDigit(nums[i]) == getMaxDigit(nums[j])) {
                    best = max(best, nums[i] + nums[j]);
                }
            }
        }
        return best;
    }
};

2816. 連結リストで表された数値を2倍にする

最初は文字列を使って2倍を計算したが、後により効率的な方法に気づいた。数値を2倍しても桁上がりは最大1桁なので、先頭ノードの値が4より大きければ新しいノードを先頭に追加する。その後、各ノードの値を2倍した結果の1の位に更新し、次のノードの値が4より大きければ現在のノードに1を加算する。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* doubleIt(ListNode* head) {
        if (head->val > 4) {
            head = new ListNode(0, head);
        }
        for (ListNode* cur = head; cur; cur = cur->next) {
            cur->val = (cur->val * 2) % 10;
            if (cur->next && cur->next->val > 4) {
                cur->val += 1;
            }
        }
        return head;
    }
};

2817. 制約条件下での最小絶対差（平衡二分探索木＋双方向ポインタ）

インデックスがx以上離れた要素間の最小絶対差を求める。スライディングウィンドウのように、現在の位置からxだけ前の要素を集合に追加していく。集合内で現在の値以上の最小値とその直前の値を比較し、最小差を更新する。境界条件を避けるため、あらかじめ集合に十分小さい値と十分大きい値を入れておく。

class Solution {
public:
    int minAbsoluteDifference(vector<int>& nums, int x) {
        int ans = INT_MAX, n = nums.size();
        set<int> seen = {INT_MIN / 2, INT_MAX};
        for (int i = x; i < n; ++i) {
            seen.insert(nums[i - x]);
            auto it = seen.lower_bound(nums[i]);
            ans = min({ans, *it - nums[i], nums[i] - *prev(it)});
        }
        return ans;
    }
};

2818. 操作でスコアを最大化する（素因数分解＋単調スタック＋繰り返し二乗法）

この問題は難易度が高く、多くの参加者が良い問題だと評価している。現時点では他の問題を優先して取り組むため、後日改めて解説を追加する予定。