Codeforces Round #134 (Div. 1) B : Blackboard Fibonacci

問題概要

X=0, Y=1が初期状態である。今、X:=X+YかY:=X+Yという操作を繰り返す。ただし初手はX:=X+Y。今、N(<10^6)回の操作後最後に代入された値がR(<10^6)になる。そのような操作列で、同じ操作が繰り替えされた回数を最小化する問題。無理なら指摘する。

解法

TwoRegisters。によく似た問題。互除法っぽく計算する。長さが丁度Nになるかは、もう一方のレジスタの値がどうなってるか全探索する。このときついでに同じ操作が繰り替えされた回数も求めておける。計算量はO(R*log R)だけどgcdなのでlogは軽く、R=10^6でも十分間に合う。

acceptされたコード

2パスでやっているけど1パスでやったほうが多分賢い。

#include <cstdio>
#include <algorithm>
#include <string>
#include <vector>
using namespace std;

int N, R;
const int INF = (int)(1.05e9); 

template<typename numType>
numType gcd(numType a, numType b) {
	for (;b != 0;) {
		numType t = a % b;
		a = b;
		b = t;
	}
	return a;
}

template<typename numType>
inline bool updateMin(numType& old, const numType& test) {
	if (old > test) {
		old = test;
		return true;
	}
	return false;
}

void init() {
	scanf("%d%d", &N, &R);
}

int countN(int a, int b) {
	if (gcd(a, b) != 1) {
		return INF;
	}
	int ret = 0;

	for (;a!=0;) {
		if (a < b) {
			swap(a, b);
		}
		ret += a / b;
		a %= b;
	}
	return ret;
}

pair<int,string> construct(int start) {
	int a = start, b = R;
	int cnt =  0;
	string str;
	const char* TB = "TB";
	int which = 0;
	for (;a!=0;) {
		if (a < b) {
			swap(a, b);
		}
		cnt += a / b - 1;
		str += string(a/b, TB[which]);
		which ^= 1;
		a %= b;
	}
	str[(int)str.length()-1] = TB[which];
	return make_pair(cnt - 1, str);
}

void solve() {
	if (R == 1) {
		if (N == 1) {
			puts("0\nT");
		}
		else {
			puts("IMPOSSIBLE");
		}
		return ;
	}
	vector<int> cands;
	for (int i = 1; i < R; ++i) {
		if (countN(i, R) == N) {
			cands.push_back(i);
		}
	}

	int mini = INF;
	string ret;

	for (int i = 1; i < (int)cands.size(); ++i) {
		pair<int, string> sub = construct(cands[i]);
		if (updateMin(mini, sub.first)) {
			ret = sub.second;
		}
	}

	reverse(ret.begin(), ret.end());
	if (ret[0] == 'B') {
		for (int i = 0; i < N; ++i) {
			ret[i] = (ret[i] == 'B' ? 'T' : 'B');
		}
	}
	if (mini < INF) {
		printf("%d\n", mini);
		puts(ret.c_str());
	}
	else {
		puts("IMPOSSIBLE");
	}
}

int main() {
	init();
	solve();

	return 0;
}