TCO 1R 500 - TwoRegisters

問題

(X,Y)＝(1,1) を初期状態とし，X+Y を X か Y のどちらかと入れ替える作業を繰り返し，目的とする数 r を作る．その作業過程を，入れ替えた側(X/Y)を並べた文字列で表す時，再短かつ辞書的に若い文字列はどうなる？

考え方

とりあえず全パターン試行は枝刈りを入れようが時間制限に引っ掛かる．
最後の１手を考えると，(r,z)→(r-z,z)となる．同様に1手ずつ前を考えると，r と z が互いに素でなかったら 1 が出てくることはない．逆に言えば r と z は必ず互いに素である．
r と z が指定されていれば，ユークリッドの互除法の原理を考えることで操作過程の文字列を作れる．そしてその1文字目がYだった場合は X と Y を全部入れ替えることで辞書的に若い方に変更できる．なので 1≦z＜r の範囲で条件を満たす文字列を探ればいい．計算量は GCD が O(log(n)) なので O(n・log(n)) で n＝10⁶ なので変に重く書かなければ大丈夫．

コード

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

class TwoRegisters
{
  int gcd(int& s, int a, int b)
  {
    s = a / b;
    int c = a % b;
    while( c ) {
      a = b;
      b = c;
      s += a / b;
      c = a % b;
    }
    s += b - 2;
    return b;
  }

  string search(int x, int y)
  {
    string cmd = "";
    while( x > 1 || y > 1 ) {
      cmd += string(x / y, 'X');
      x %= y;
      if( x <= 1 && y <= 1 ) break;
      cmd += string(y / x, 'Y');
      y %= x;
    }
    cmd.resize(cmd.size() - 1);
    reverse(cmd.begin(), cmd.end());
    if( cmd[0] == 'Y' ) {
      for( int i = 0 ; i < cmd.size() ; ++i ) cmd[i] = (cmd[i] == 'X') ? 'Y' : 'X';
    }
    return cmd;
  }

public:
  string minProg(int r)
  {
    switch( r ) {
    case 0: return "";
    case 1: return "";
    }
    string best = string('X', r - 1);
    for( int i = r - 1 ; i >= 1 ; --i ) {
      int step;
      if( gcd(step, i, r) != 1 || step > best.size() ) continue;
      string cmd = search(r, i);
      if( cmd.size() < best.size() || (cmd.size() == best.size() && cmd < best) ) {
          best = cmd;
      }
    }
    return best;
  }
};