UTPC2012 : K - ラッピング

UTPCもようやく終盤。
http://utpc2012.contest.atcoder.jp/tasks/utpc2012_11

立方体にリボンを巻くときの長さを求める問題。
smallは回答見ずに解けたので、まずはsmallから。

まず前提として、事前にリボンの方向(A,B)は互いに素で、0

Small

立体状でリボンが巻きつくのを考えるのは大変なので、リボンは平面上で一直線においてあって、立方体がリボンの位置に合わせて転がると考える。

リボンが右上方向に傾きA/Bで置いてあると考えると、リボンに沿って立方体を右にB回、上にA回転がすと表面の正方形上で開始した位置と同じ場所で戻る。
この処理は、１回右に転がすたびに上に転がす必要があるか求めるのでO(B)で処理できる。

ただ、右にB回、上にA回転がした場合に立方体の向きが最初と同じかわからないので、「右にB回・上にA回転がす」の処理を何回行うと初期状態に戻るか求めればよい。
仮にN回行うと初期状態に戻るとすると、合計で右にNB回、上にNA回転がすのでその長さはとなる。

ll A,B;
ll gcd(ll a, ll b) { return (b==0)?a:gcd(b,a%b);}
 
int face[6]; //上面・右・下・左・奥・手前の順
 
void rot_right(){
	swap(face[0],face[1]);
	swap(face[0],face[2]);
	swap(face[0],face[3]);
}
void rot_up(){
	swap(face[0],face[4]);
	swap(face[0],face[2]);
	swap(face[0],face[5]);
}
int num_ret() {
	int to[6],nface[6],i,nl=1;;
	FOR(i,6) to[face[i]]=i;
	FOR(i,6) nface[i]=face[i];
	
	while(1) {
		int ok=1;
		FOR(i,6) if(nface[i]!=i) ok=0;
		if(ok) return nl;
		nl++;
		FOR(i,6) nface[to[i]]=face[i];
		FOR(i,6) face[i]=nface[i];
		
	}
}

void solve() {
	int x,y,i,j,res,TM,nc;
	ll numloop;
	vector<int> rotpat;
	
	scanf("%lld%lld",&A,&B);
	if(A==0 || B==0) {
		_P("%.7lf\n",4.0);
		return;
	}
	
	ll g = gcd(A,B);
	A/=g; B/=g;
	if(A>B) swap(A,B);
	if(B>100000) return;
	
	FOR(i,6) face[i]=i;
	ll TA=0;
	FOR(i,B-1) {
		if((TA+A)/B != TA/B) rot_up();
		TA+=A;
		rot_right();
	}
	
	rot_right();
	rot_up();
	
	double nl = num_ret();
	double DA = A, DB = B;
	_P("%.8lf\n",nl*sqrt(DA*DA+DB*DB));
	
	return;
}

Large

Smallの手法はO(B)の時間がかかるので、B<=10^18では時間切れになる。
「右にB回・上にA回転がす」をもっと速く終える必要がある。
ここは解説の手法を使おう。
上に転がすのは右にB/A回転がした時だが、このさい上方向に(B%A)/Aだけリボンが進んだ状態になるので、次は(B-(B%A))/A回右に転がした場合になる。
この考えを突き詰めるとユークリッドの互除法の様に剰余を取って回転処理を畳み込んでいくことになる。

キモになるコードは、解説の最終ページにある。拡張ユークリッドの互除法みたいな容量で回転処理を畳み込んでいるね。

ll A,B;
ll gcd(ll a, ll b) { return (b==0)?a:gcd(b,a%b);}


vector<int> mult(vector<int>& l, vector<int>& r) {
	vector<int> res;
	int i;
	FOR(i,6) res.push_back(r[l[i]]);
	return res;
}

vector<int> pow(vector<int>& l, ll num) {
	vector<int> res,tmp;
	int i;
	FOR(i,6) res.push_back(i);
	tmp=l;
	while(num) {
		if(num&1) res = mult(res, tmp);
		tmp = mult(tmp, tmp);
		num >>= 1;
	}
	return res;
}

vector<int> calc(ll a, ll b, vector<int>& pata, vector<int>& patb) {
	if(b==0) return pata;
	if(a==0) return patb;
	if(a>=b){
		vector<int> tmp1=pow(pata,a/b);
		vector<int> tmp2=mult(tmp1,patb);
		return calc(a%b, b, pata,tmp2 );
	}
	else {
		vector<int> tmp3=pow(patb,b/a);
		vector<int> tmp4=mult(pata,tmp3);
		return calc(a, b%a, tmp4, patb);
	}
}

int num_ret(vector<int>& rotpat) {
	vector<int> res;
	int i,nl=1;
	FOR(i,6) res.push_back(rotpat[i]);
	
	while(1) {
		int ok=1;
		FOR(i,6) if(res[i]!=i) ok=0;
		if(ok) return nl;
		nl++;
		res = mult(res,rotpat);
	}
}

void solve() {
	int x,y,i,j,res,TM,nc;
	ll numloop;
	//0:接地 1:面の反対 2,3,4,5:上右下左
	int rotrpat[6] = {5,3,2,0,4,1};
	int rotupat[6] = {4,2,0,3,1,5};
	vector<int> rotr, rotu, rotpat;
	
	FOR(i,6) rotr.push_back(rotrpat[i]),rotu.push_back(rotupat[i]);
	
	
	scanf("%lld%lld",&A,&B);
	if(A==0 || B==0) {
		_P("%.7lf\n",4.0);
		return;
	}
	
	ll g = gcd(A,B);
	A/=g; B/=g;
	
	rotpat = calc(A,B,rotr,rotu);
	
	double nl = num_ret(rotpat);
	double DA = A, DB = B;
	_P("%.8lf\n",nl*sqrt(DA*DA+DB*DB));
	
	return;
}

まとめ

幾何の問題と見せかけて、整数問題に落とし込めるのが面白い。
こんなの本番中に思いつかないよ…。