kmjp's blog

競技プログラミング参加記です

Codeforces #509 Div2 F. Ray in the tube

こちらも3000ptにしては簡単。
http://codeforces.com/contest/1041/problem/F

問題

2つのX軸に平行な直線y=y1とy=y2で挟まれた空間中に反射するレーザーを放つ。
レーザーの放ち方は、両直線上の格子点を1つずつ選び、片方から片方に向けレーザーを放つ。

ここで、両直線上にいくつかの点が存在する。
レーザーを最適に放った場合、最大いくつの点を通過させられるか。

解法

両直前上の点のペアを結ぶようレーザーを放てば最低2点は通る。
よって解の最小値は2である。こうしておくと、真上にレーザーを放つケースを気にしなくてよくなる。

(x,y1)から(x+a*2^b,y2)にレーザーを放ったとする。ただしaは奇数でbは0以上の値とする。
xを十分小さい位置と考えれば、X座標が負の向きにレーザーを放つケースは考えなくてよい。

ここで、aが3以上のケースは考えなくてよい。
なぜなら、(x+2^b,y2)に向けてレーザーを放てば、(x+a*2^b,y2)が通過する直線上の点はすべて通過するためである。
よって、(x,y1)から(x+2^b,y2)にレーザーを放つケースのみ考えればよい。
これは両直線上の点の座標(x,y)をx mod 2^(b+1)で分類して数え上げれば最大値が求められる。

int N,M;
ll A[101010],B[101010];


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>x;
	FOR(i,N) cin>>A[i];
	cin>>M>>x;
	FOR(i,M) cin>>B[i];
	
	int ret=2;
	for(ll L=2;L<=1LL<<40;L<<=1) {
		map<ll,int> mp;
		FOR(i,N) mp[A[i]%L]++;
		FOR(i,M) mp[(B[i]+L/2)%L]++;
		
		FORR(m,mp) ret=max(ret,m.second);
	}
	
	cout<<ret<<endl;
	
}

まとめ

今回参加しておけばよかったな。