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; }