Codeforces #325 Div1 C. Alice, Bob, Oranges and Apples

これは自分では思いつかんな…。
http://codeforces.com/contest/585/problem/C

問題

初期状態でAliceはミカンを1つ、Bobがリンゴを1つ持っている。
また、かごには大量のミカンとリンゴがある。

ここで以下のゲームを行った。

• AかBかが書かれたカードが何枚かあり、順に開いていく。
• Aが書かれている場合、Aliceは手持ちの果物をすべてBobに渡し、カゴから同数のミカンを取る。
• Bが書かれている場合、Bobは手持ちの果物をすべてAliceに渡し、カゴから同数のリンゴを取る。

ゲームを終えたとき、両者の持っているミカンの合計はX、リンゴの合計はYであった。
カードの登場順を答えよ。

解法

X,Yの最大公約数が1以外の時解はない。
それ以外の場合必ず解がある。

以下Editorialを見て回答。
Editorialを見ると、ある時点で両者のミカンの和をa,リンゴの和をbとし。
b/aという規約有理数を考える。
どちらかのカードを開くということは、それぞれ(0/1,1/0)の２値のうちどちらかを中間数に置き換えるという処理に相当する。
そしてその処理はStern-Brocot木を左右どちらかにたどることに相当する。

逆にStern-Brocot木でY/Xに到達可能であるなら、その際の左右到達順がそのまま解になる。
以下の処理を再帰的に行う。

• Y==1ならX-1回左(カードA)を取ればよい。
• X==1ならY-1回右(カードB)を取ればよい。
• XもYも1以外の場合:
  • X＞YならX/Y回左(カードA)を取ればよい。そして残り(Y%X)/Yに到達する方法を再帰的に求める。
  • X＜YならY/X回右(カードB)を取ればよい。そして残り(X%Y)/Xに到達する方法を再帰的に求める。

void dfs(ll X,ll Y) {
	if(X>Y) {
		if(Y==1) cout<<(X-1)<<"A"<<endl;
		else {
			cout<<X/Y<<"A";
			dfs(X%Y,Y);
		}
	}
	else {
		if(X==1) cout<<(Y-1)<<"B"<<endl;
		else {
			cout<<Y/X<<"B";
			dfs(X,Y%X);
		}
	}
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	ll X,Y;
	
	cin>>X>>Y;
	if(__gcd(X,Y)>1) return _P("Impossible\n");
	dfs(X,Y);
	
}

まとめ

Stern-Brocot木、初の概念なので理解しておきたいな。