LeetCode Weekly Contest 382 : 3022. Count the Number of Houses at a Certain Distance II

最近急に難易度8が増えてきたな。
https://leetcode.com/contest/weekly-contest-382/problems/minimize-or-of-remaining-elements-using-operations/

問題

整数列Aが与えられる。
隣接する2要素を選択肢、両者のandを取った1要素に置き換える処理を最大計K回行えるとする。
その後の全要素のorを最小化せよ。

解法

上のbitから定めて行く。
「このbit群を落とすには、計K回以下の置き換えで済むか」を順次見て行けばよい。

class Solution {
public:
    int minOrAfterOperations(vector<int>& nums, int k) {
		int ret=0;
		int i;
		for(i=29;i>=0;i--) {
			int tmp=ret+(1<<i);
			int cnt=0;
			int la=0;
			FORR(a,nums) {
				int v=a&tmp;
				if(la==0) la=v;
				else la&=v;
				if(la) cnt++;
			}
			
			if(cnt<=k) ret=tmp;
		}
		return ret^((1<<30)-1);
        
    }
};

まとめ

LeetCodeは、コードが短くても普段出ないタイプの問題は難易度高めに判定される傾向がある気が。