ICPC 2017 国内予選F: リボンたたみ

解法

f:id:pekempey:20170717194455p:plain

LRどちらを行っても下から何番目にあるのかは変わらない。そのため、各レベルにおいて下から何番目であるのかを求めることは容易である。

広げきった状態から一手前の状態を考える。一手前の状態で下半分にあった場合、Lをすれば当然右半分に移動し、Rをすれば左半分に移動するはずである。
よって左半分にあるか右半分にあるかが分かればL,Rのどちらの操作を行ったかが分かる。

一手前が上半分にあった場合も同様に求めることができる。

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>

int main() {
	while (true) {
		long long n, x, y;
		std::cin >> n >> y >> x;
		if (n == 0) break;
		x--;
		y--;
		y = (1LL << n) - 1 - y;

		std::vector<int> which;
		for (long long i = 1LL << n; i != 1; i >>= 1) {
			if (y < i / 2) {
				which.push_back(0);
			} else {
				which.push_back(1);
				y = i - 1 - y;
			}
		}
		std::reverse(which.begin(), which.end());

		std::string ans;
		for (int i = 0; i < n; i++) {
			long long len = (1LL << n) / (1LL << i);
			if (which[i] == 0) {
				if (x < len / 2) {
					ans += 'R';
				} else {
					ans += 'L';
				}
				x %= len / 2;
			} else {
				if (x < len / 2) {
					ans += 'L';
				} else {
					ans += 'R';
				}
				x = len / 2 - 1 - x % (len / 2);
			}
		}

		std::cout << ans << std::endl;
	}
}