ICPC2017 国内予選 F リボンたたみ

問題

日本語なので略
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1621&lang=jp

解法

しるしのついたリボンをほどいていくことを考える。
重要な考察として、リボンをほどいていくとき、しるしのついた位置のリボンが上半分にあるか、下半分にあるかは、リボンを折るときに左から折ったか、右から折ったかに依らない。ただ上から何番目にあったかだけ
に依存する。
（具体的には二進数の最上位ビットの有無を見ればよい。上側にあった場合上側のリボンは全てひっくり返るのでほどいた後順番が逆になる。）

そうすると、それぞれの折り畳みのときに上にあったか下にあったかの列を作るすることができる。
リボンを折り畳んでいくとき、左半分にあるか右半分にあるかと、折り畳み後に上半分にあるか下半分にあるかを両方知ることができるので、リボンを折り畳む操作の列が復元することができる。

ソースコード

int main(){
	int n;
	ll from, to;
	while(cin >> n >> from >> to, n){
		from--; to--;
		
		vi upper;
		string ans;
		rep(i, n) if(from >> (n - i - 1) & 1) upper.pb(0);
		else{
			upper.pb(1);
			from = ~from; //上側にあったらほどくと順序が逆になる
		}
		reverse(all(upper));
		rep(i, n){
			//（左, 右）半分から（上, 下）側にくるかで場合分け
			ans.pb((to >> n - i - 1 & 1) == upper[i] ? 'R' : 'L');
			if(upper[i]) to = ~to; //上に来たら左右の位置は逆になる
			to &= (1ll << (n - i)) - 1; //ビット反転のときによけいなビットまで立てたので消す。
		}
		cout << ans << endl;
	}
	
	return 0;
}