Entries

スポンサーサイト (この記事を編集する[管理者用])

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/1374-b50187bc
この記事にトラックバックする(FC2ブログユーザー)

Open 2010 Round 1 MEDIUM - TwoRegisters (この記事を編集する[管理者用])

Source

TopCoder Open 2010 Algorithm Round 1 MEDIUM (500pt)
Problem Statement
Open 2010 Algorithm Round 1 自分の参加記録

問題概要

最初x=1, y=1になっている.
命令Xを行うとxにx+yが代入される.
命令Yを行うとyにx+yが代入される.
x=rとするための,命令数最小の命令列を求める問題.
複数あるなら,辞書順最小のものを求める.
rは1以上1000000以下.

解法

逆から考えれば前の状態は一意に定まる.
なので,最終状態がX=r, Y=i (i=1,2,...,r)の場合に必要なステップの数を最初に計算する.
それは,ユークリッドの互除法っぽくO(log r)で計算できる.
そして,最小ステップ数を達成するもののみ,実際に,命令列を復元して,辞書順最小のものを求める.

C++によるスパゲッティなソースコード
// #includeとusing namespace std;は略

#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

int cal(int a,int b){
  int res=0, tmp;
  while(a>1 || b>1){
    if(a==b){ res=100000000; break; }
    if(a>b){ tmp = (a-1)/b; res += tmp; a -= tmp*b; }
    else if(a<b){ tmp = (b-1)/a; res += tmp; b -= tmp*a; }
  }
  return res;
}

string solve(int a,int b){
  string res;
  while(a>1 || b>1){
    if(a>b) res += "X", a-=b;
    else    res += "Y", b-=a;
  }
  reverse(res.begin(), res.end());
  return res;
}

int memo[1111111];

class TwoRegisters {
public:
string minProg(int r) {
  int i,k,max_len;
  string res="http://rsujskf.blog32.fc2.com/";
  string tmp;

  max_len = r+10;
  REP(i,1,r+1){
    k=cal(r,i);
    if(max_len > k) max_len = k;
    memo[i] = k;
  }

  for(i=r;i>=1;i--){
    if(memo[i]!=max_len) continue;
    tmp = solve(r,i);
    if(tmp < res) res=tmp;
  }

  return res;
}

};

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/1374-b50187bc
この記事にトラックバックする(FC2ブログユーザー)

Appendix

Recent Articles

ブログ内検索

Ads


(プライバシーポリシー)
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。