TopCoder Open Round 1 Medium TwoRegisters

TopCoder

問題概要

二つのレジスタX,Yを持つ単純なコンピュータがある。
X,Yの初期値は1で、次の二つの命令が可能である。

X
XにYを足す
Y
YにXを足す

このとき与えられた数rをレジスタXに作るための、長さ最小で、かつその中でアルファベット順で最初にくる命令列を求めよ。


r≦10^6である

解法

Xがrになる直前のYの値を決めると命令が復元できる。


……一意にorz
メモ化する必要ねーじゃん。


なので、Yレジスタの値を1からrまで試して（ただしGCDが1でないものはありえないので飛ばす）、命令が最小の長さになるようなYレジスタを列挙して、
次に具体的に命令を作る。命令の長さはせいぜい100とか200のようなので単純な実装でよい。

ソースコード

int calc(int a,int b)
{
	if(a<b)swap(a,b);
	if(b==0)return 0;
	
	return calc(b,a%b)+a/b;
}
void build(string &s,int x,int y)
{
	if(x==1&&y==1)return;
	s.pb(x>y?'X':'Y');
	
	if(x>y)build(s,x-y,y);
	else build(s,x,y-x);
}

class TwoRegisters {
	public:
	string minProg(int r) 
	{
		if(r==1)return string();
		
		int mnlen=inf,len; vi mni;
		for(int i=1;i<r;i++)if(__gcd(r,i)==1)
		{
			len=calc(r,i);
			if(len<mnlen)mni.clear(),mnlen=len;
			if(len==mnlen)mni.pb(i);
		}
		
		string ans;
		rp(i,mni)
		{
			string tmp;
			build(tmp,r,mni[i]); reverse(all(tmp));
			if(ans.empty()||tmp<ans)ans=tmp;
		}
		return ans;
	}
};