Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

SRM526.5 DIV2 HARD - MagicNaming (この記事を編集する[管理者用])

Source

TopCoder SRM526.5 DIV2 EASY (1000pt)
Problem Statement

問題概要

アルファベット小文字のみからなる50文字以下の文字列が与えられる.
それは,n個の単語を,繋げたもので,繋げ方n!通りある中の,繋げたあとの文字列が辞書順で最小になるように繋げたものである.
考えうるnの最大値を求める問題.

解法

例えば,文字列A, B, C, Dを繋げた時,ABCDが辞書順最小になるための必要十分条件は
 AB ≤ BA, BC ≤ CB, CD ≤ DC
と2つの隣り合う文字列をひっくり返しても,辞書順で早くならないことである.
ということで,最後に使った単語の場所を状態として,それ以降の文字列を最大で何個に分割できるかというDPをすれば良い.

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

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

string in;
int len;
int dp[60][60];

int solve(int depth, int last){
  int i,j,k;
  int res = -10000, tmp;
  string a, b;

  if(dp[depth][last] != -1) return dp[depth][last];
  if(depth==len) return dp[depth][last] = 0;

  a = in.substr(last, depth-last);
  
  REP(i,depth+1,len+1){
    b = in.substr(depth,i-depth);
    if(a+b > b+a) continue;
    tmp = solve(i, depth) + 1;
    if(tmp < 0) continue;
    if(res < tmp) res = tmp;
  }

  return dp[depth][last] = res;
}

class MagicNaming {
public:
int maxReindeers(string magicName) {
  int i,j;

  in = magicName;
  len = in.size();
  rep(i,60) rep(j,60) dp[i][j] = -1;
  return solve(0, 0);
}

};

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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