[LeetCode] Weekly Contest 280 復習

はじめに

LeetCode Weekly Contest 280 の復習記事です。

今回は過去にないレベルで解けず（問題が比較的難しかったというのもありますが）、コンテスト中に解けたのはなんと 1 問目だけでした…。流石に凹んだのでちゃんと復習しようと思ってこの記事を書きました。

2169. Count Operations to Obtain Zero

難易度

Easy

アプローチ

なんの捻りもないので、問題文の指示通りにコードを書くだけの問題です。

解答

class Solution {
public:
    int countOperations(int num1, int num2) {
        int res = 0;
        
        while (num1 != 0 && num2 != 0) {
            if (num1 >= num2) {
                num1 -= num2;
            } else {
                num2 -= num1;
            }
            res++;
        }
        
        return res;
    }
};

2170. Minimum Operations to Make the Array Alternating

難易度

Medium レベルですが、私はコンテスト中に解けなかったです。考察は近いところまで出来たのですがあと一歩足りなかったようです。

アプローチ

問題文が若干解りづらいのですが、結局は偶数番目と奇数番目の 2 グループに分けて考えて、それぞれのグループの数値を同じにするための最小回数を求める問題です。

まず、偶奇それぞれで各数値の出現回数を調べ、最多となる出現回数の数値にそれ以外の数値を変更する回数が求める最小回数となります。ただし、Example 2 のように偶奇で最多出現回数が同じ数値になるケースにおいては、同じ数値にならないような組み合わせの数値にする必要があります。私はコンテスト中にこの求め方が分からなかったのですが、他の解答を見ると普通に O(N^2) ? の全探索をしているようでした...。あとエッジケースとして、全ての数値が同じ場合も注意が必要です。

解答

class Solution {
public:
    int minimumOperations(vector<int>& nums) {
        int n = nums.size();
        unordered_map<int, int> counter_odd, counter_even;
        
        // 各数値の出現回数をカウント
        for (int i = 0; i < n; i++) {
            if (i & 1) {
                counter_even[nums[i]]++;
            } else {
                counter_odd[nums[i]]++;
            }
        }
        
        // 出現回数の大きい順にソートするために一旦配列に入れ直す
        vector<pair<int, int>> odd, even;
        for (auto& [k, v] : counter_odd) {
            odd.push_back({v, k});
        }
        for (auto& [k, v] : counter_even) {
            even.push_back({v, k});
        }

        // 候補となる数値は大きい順となるので降順にソート
        sort(odd.begin(), odd.end(), greater<>());
        sort(even.begin(), even.end(), greater<>());

        // odd/evenの候補となる数値が被っていないペアを全探索する
        for (auto& o : odd) {
            for (auto& e : even) {
                if (o.second != e.second) {
                    return n - o.first - e.first;
                }
            }
        }
        
        // エッジケース: 全ての数値が同じだった場合
        return n / 2;
    }
};

2171. Removing Minimum Number of Magic Beans

難易度

Medium

アプローチ

コンテスト中は問題を誤読していました…。結果解けず…。

まず、各バックbeans[i]から豆をいくつか取り出し、残った豆の値が0, 0以外のいずれかの数値の1種類のいずれかにする必要があります。ここでポイントとなるのが "0以外の候補になる数値はbeans配列の中のいずれかの数値である" ということです。

分かり易くするためにbeans[i]を昇順にソートします。直感的に分かりそうではありますが、あるbeans[i]までは全て豆を取り出し、それ以降はbeans[i]に値を揃えるためにbeans[i + 1] - beans[i], beans[i + 2] - beans[i], ... だけ豆を取り出す必要があります。そのため、beansに存在しない数値に揃えようとすると存在する数値の場合よりも余計に取り出す必要があることがわかります。

つまり、ソート後のbeans配列の各要素に対して、インデックスiより前の要素についてはbeans[0] + .. + beans[i - 1] だけ豆を取り出し、インデックスi以降の要素については(beans[i] + .. + beans[n - 1]) - (n - i) * beans[i]だけ豆を取り出すことになります。

この計算式を単純化すると、sum(beans) - (n - i) * beans[i]となります。この計算結果の最小値が求める答えになります。

解答

class Solution {
public:
    long long minimumRemoval(vector<int>& beans) {
        long long n = beans.size();
        long long sum = accumulate(beans.begin(), beans.end(), 0LL);
        long long res = LLONG_MAX;

        sort(beans.begin(), beans.end());
        for (int i = 0; i < beans.size(); i++) {
            res = min(res, sum - (n - i) * beans[i]);
        }
        
        return res;
    }
};

2172. Maximum AND Sum of Array

難易度

Hard レベル。コンテスト中は問題すら見ていませんでしたが、Hard の中では比較的簡単なのではないかと感じます。

アプローチ

入力制約を見てみると結構緩いので普通の backtracking でイケるかもと思いましたが、試してみると TLE だったので、メモ化作業が必要でした。ということでこの問題はメモ化 + backtracking のアプローチで解けます（もしくは DP)。

解答

map のキーに vector を直接突っ込んでいますが、最適解は bitmask を利用することだと思われます。時間があれば更新します。

class Solution {
public:
    int maximumANDSum(vector<int>& nums, int numSlots) {
        int n = nums.size();
        vector<int> slots(numSlots, 0);
        map<vector<int>, int> memo;
        return backtracking(nums, numSlots, 0, slots, memo);
    }

private:
    int backtracking(vector<int>& nums, int& numSlots, int cur, vector<int>& slots, map<vector<int>, int>& memo) {
        if (cur >= nums.size()) {
            return 0;
        }

        if (memo.find(slots) != memo.end()) {
            return memo[slots];
        }

        int res = 0;
        for (int i = 0; i < numSlots; i++) {
            if (slots[i] < 2) {
                slots[i]++;
                res = max(res, ((i + 1) & nums[cur]) + backtracking(nums, numSlots, cur + 1, slots, memo));
                slots[i]--;
            }
        }
        return memo[slots] = res;
    }
};