SRM 596

250

要素がすべて0であるような配列に対して、「配列の要素一つに対して1増やす操作」(操作1)と、「配列のすべての要素を2倍する」(操作2)という操作を繰り返して、与えられた配列にする。
必要な操作の回数の最小値を求めよ。

例えば、二進法で{10100}は、操作を1,2,2,1,2,2の順で行うと6回で作れます。(最初の操作2は操作1でも良いですが、操作2にしたほうがうれしいです。)操作1は1の個数、操作2は(桁数-1)回必要です。
要素が複数の場合も同様ですが、操作2は、全体で共通なので、最も桁数が大きいものに合わせればよいです。
よって、答えは、(1の個数の和)+(最も桁数が大きい数字の桁数-1)になります。
与えられた配列がすべて0のときは、0です。

class IncrementAndDoubling {
public:
	int getMin( vector <int> s ) {
		int ans = 0,sh = 0;
		for(int i = 0; i < s.size(); i++){
			for(int j = 1; s[i]; j++,s[i]>>=1){
				if(s[i]&1){
					ans++;
					sh = max(sh,j);
				}
			}
		}

		return max(ans+sh-1,0);
	}
};

500

要素の個数がNの集合Sに含まれる任意の2つの異なる要素A,Bは、A&B > 0を満たし、任意の3つの異なる要素A,B,CはA&B&C = 0 を満たすようなSのうち、辞書順最小のものを出力する。(解がないときは、空の配列を返す)

与えられたものが条件を満たしているかを確認したあと、貪欲法で解けます。
A&B&C = 0 は、X&(1LL<

int used[100];
int M = 60;

class BitwiseAnd {
public:
	vector<long long> lexSmallest( vector<long long> s, int N ) {
		vector<ll> emp;
		memset(used,0,sizeof(used));
		if(s.empty()) s.push_back((1LL<<(N-1))-1);
		for(int i = 0; i < s.size(); i++){
			for(int j = 0; j < i; j++){
				ll p = s[i]&s[j];
				if(!p) return emp;
				for(int k = 0; k < j; k++){
					if(p&s[k]) return emp;
				}
			}
		}
		for(int i = 0; i < s.size(); i++){
			int cnt = 0;
			for(int j = 0; j < M; j++){
				if(s[i]&(1LL<<j)){
					used[j]++;
					cnt++;
					if(used[j]>2)return emp;
				}
			}
			if(cnt<N-1) return emp;
		}

		while(s.size()<N){
			ll t = 0;
			for(int i = 0; i < s.size(); i++){
				for(int j = 0; j <= M; j++){
					if(j==M) return emp;
					if((s[i]&(1LL<<j)) && used[j]==1){
						t |= 1LL<<j;
						used[j]++;
						break;
					}
				}
			}
			for(int i = 0,j = 0; i < N-s.size()-1; i++){
				while(used[j]&&j<M)j++;
				if(j==M) return emp;
				t |= 1LL<<j;
				used[j]++;
			}
			s.push_back(t);

		}

		sort(s.begin(),s.end());
		return s;

	}
};

ox- 214.88 + 50.0 = 264.88
1742 -> 1777