CF509 F - Ray in the tube

Codeforces
問題

y=yaとy=ybに挟まれた領域(チューブ)がある
このチューブの両側の壁上にいくつかのセンサーが付いている (x座標は非負整数)
両側の壁上の任意の格子点を2つ選び、それらを通るようなレーザーを放射するとき、最大で何個のセンサーに同時に光を入射できるか求めよ
(レーザーの光は壁に当たる度に弱まることなく反射する)

1 <= 上下それぞれの壁に付いているレーザーの個数n,m <= 10^5
0 <= レーザーの座標x <= 10^9

解法

レーザーを作る2点のx座標の差をdxとすると、dxは2のべき乗だけ試せば十分
(∵ dx = 2^k * p(:奇数)として通るセンサーはdx = 2^kとしても通るから)
座標が全部10^9以下だからdxの候補は30個くらいしかない
dxを固定したら、片側の壁はa[i]%2dx、もう片側の壁は(b[i]+dx)%2dxの値が同じセンサーは全て一本のレーザーで通れる
この値の個数をmapで数えて最大値で答えを更新していけばいい

ちなみに2つの壁のy座標は問題を解くために必要ない情報 どうでもいい

実装

両側の壁にセンサーが1個ずつあってそれらのx座標が同じときなんかは答えは2になるけど↑だけだと1になってしまう
これを防ぐために答えの初期値は2にしとく

↑で言ったdxは↓のコードではx

int n, ya, a[100100], m, yb, b[100100], res = 2, x = 1;

signed main() {
	cin >> n >> ya;
	rep(i,n) cin >> a[i];
	cin >> m >> yb;
	rep(i,m) cin >> b[i];
	rep(k,31) {
		map<int,int> p;
		rep(i,n) p[a[i]%(2*x)]++;
		rep(i,m) p[(b[i]+x)%(2*x)]++;
		each(i,p) chmax(res, i.se);
		x *= 2;
	}
	cout << res << endl;
}