Beta Round #68-C: Chessboard Billiard

問題概要

N,M(<10^6)マスのボードでビリヤードをする。ただし斜め45度にしか打てない。どの玉を撞いても他の玉に当たらないような配置をとったとき、玉は最大でいくつ置けるか求める問題。

解法

反射の問題が出たら大抵鏡像を考えると上手くいく。スタート地点は一般にもっとも左のマスにあると考えて良いので、あとは座標(0,i)から撞いた玉がどこの(0,j)に行くのかを定数時間で計算すれば良い。左右の壁に2回当たったら戻ってくるので、

大体図のようになる。青の部分は上下が反転している(ちなみに右の長方形は左右が反転している)。後はつないでお終い。gcd使うと1行で書けるらしいけどよく分かっていない。

感想

何でこんな簡単な問題がコンテスト中に通せなかったのかというと、「右の端点が赤に入っているときはそのままで青に入っているときはN-1-xで置き換えて…」とかやってバグにハマっていた。当然赤と青を二個一組で考えるべきだった。

#include <cstdio>
using namespace std;

typedef long long int64;

const int MAX_UF = 2000007;
int pars[MAX_UF];
void init(int n){for(int i=0;i<n;i++)pars[i]=i;}
int getRoot(int x){return x==pars[x]?x:(pars[x]=getRoot(pars[x]));}
bool isSame(int x, int y){return getRoot(x)==getRoot(y);}
void merge(int x, int y){pars[getRoot(x)]=getRoot(y);}
bool visited[MAX_UF];

int N, M;

void proc(int ii){
	if(visited[ii]) return ;
	visited[ii] = true;
	int n = ((ii+2*(M-1))%(2*N-2)+(2*N-2))%(2*N-2);
	merge(ii,n);
	proc(n);
	n = ((ii-2*(M-1))%(2*N-2)+(2*N-2))%(2*N-2);
	merge(ii,n);
	proc(n);
}

int solve(){
	init(2*(N-1));
	int ans = 0;
	for(int i=1; i<N; i++){
		merge(i, 2*(N-1)-i);
	}
	for(int i=0; i<N; i++){
		proc(i);
	}
	for(int i=0; i<2*(N-1); i++)if(getRoot(i)==i){
		ans++;
	}
	return ans;
}

int main(){
	scanf("%d%d",&N,&M);
	printf("%d\n", solve());
	return 0;
}