kmjp's blog

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

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)の2値のうちどちらかを中間数に置き換えるという処理に相当する。
そしてその処理は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木、初の概念なので理解しておきたいな。