Codeforces Round #586 D. Alex and Julian

Problem - D - Codeforces

概要

整数集合Bが与えられる。1から始まる全ての整数をグラフの頂点と考え、|i - j| ∊ B であれば、iとjに辺を結んでいく。
このときできるグラフを2部グラフをするために、Bから要素を消去することを考える。消去すべきBの要素の個数と、消去すべきBの要素を列挙せよ。

制約

1 ≦ N ≦ 2 * 10^5
1 ≦ B[i] ≦ 10^18

方針

まずBが全て奇数である場合は、2部グラフになる。
例①：B = {1, 3, 5}
B = 1 : 1-2, 2-3, 3-4, 4-5, ...
B = 3 : 1-4, 2-5, 3-6, 4-7, ...
B = 5 : 1-6, 2-7, 3-8, 4-9, ...
⇒全て奇数-偶数という辺の張られ方をしているため、{1, 3, 5, 7, ...}, {2, 4, 6, 8, ...} と頂点を分けると、各集合内で辺は張られない。

これに一つでも偶数が含まれると、2部グラフにならない。
B = 2 : 1-3, 2-4, 3-5, 4-6, ...
⇒奇数-奇数, 偶数-偶数の辺が張られてしまう。

偶数の場合については、Bの各要素について「何回2で割れるか」が全て同じ場合は、2部グラフになる。
理由としては、辺が張られる頂点同士の差を2で割れるだけ割ると、上記の奇数の張り方に帰着するため。
例②：B = {2, 6, 10}
B = 2 : 1-3, 2-4, 3-5, 4-6, 5-7, ...
B = 6 : 1-7, 2-8, 3-9, 4-10, ...
B = 10 : 1-11, 2-12, 3-13, 4-14, ...
⇒{1, 2, 5, 6, 9, 10, ...}, {3, 4, 7, 8, 11, 12, ...}と頂点を分けると、各集合内で辺は張られない。

よって、Bの各要素について「何回2で割れるか」を集計し、最も多い「何回2で割れるか」の個数の要素をBに残せばよい。
「何回2で割れるか」はビルトイン関数の__builtin_ctzllを使用するとよい。

解答

Submission #60951496 - Codeforces

#include <bits/stdc++.h>
#define rep(i,n) for(int i=(0);i<(n);i++)
 
using namespace std;
 
typedef long long ll;
 
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
 
	int n;
	cin >> n;
 
	ll b[n];
	rep(i, n) cin >> b[i];
 
	vector<int> ctzs(100, 0);
	rep(i, n) ctzs[__builtin_ctzll(b[i])]++;
 
	int mx = 0;
	int mxctz = 0;
	rep(i, 100){
		if(ctzs[i] > mx){
			mx = ctzs[i];
			mxctz = i;
		}
	}
 
	cout << n - mx << endl;
	int cnt = 0;
	rep(i, n){
		if(__builtin_ctzll(b[i]) != mxctz){
			cnt++;
			cout << b[i] << ((cnt == n - mx) ? "\n" : " ");
		}
	}
}