Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

SRM563 DIV1 EASY - FoxAndHandle (この記事を編集する[管理者用])

Source

TopCoder SRM563 DIV1 EASY (300pt)
Problem Statement

問題概要

文字列AとBを混ぜて文字列Xを作るとは,
 Xの部分列(部分文字列ではない)としてAが存在して,その部分列を取り除いた文字列は(順番を入れ替えずに)Bに一致させることができる
50文字以下の文字列Sが与えられる.
Sにはアルファベット小文字しか含まず,各文字の種類について,含まれる数は偶数個.
Tと,Tの置換(なんでも良い)を混ぜるとSになるTのうち,辞書順最小のものを求める問題.

解法

Tの1文字目がaにできるかどうか,できなければbにできるかどうか,と判定していって辞書順最小のものを探す.
Tの1文字目がaにできるためには,Sの最初のaを探してそれを使うことにする.
最初のaより前の文字は,Tの置換にしか利用できず,それより後ろのはどちらにも利用できる.
それより後ろのを全部Tに利用したとして,Tに含まれるべき文字が全部含まれるかどうかをチェックする.
2文字目がaにできるかどうかを調べるときは,Sの最初のaを探していたところを,前回使った文字以降で最初のaを探すようにすれば良い.

以下のコードでは,使える文字の中で最小のものを探して,それを1文字目に使って,それに対応するTの置換のをどれにするか全部試した.
愚直に全部試すとTLEすると思うので,適当にメモ化した.
計算量見積もれないけど遅くない.

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

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

map<string, string> memo;

string solve(string S, string A){
  int i, j, k, n, deled;
  int cnt[26], can[26];
  string res = "zzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz", mem = S + " " + A;
  string tmp;
  char mn;

  if(S=="") return "";
  if(memo.count(mem)) return memo[mem];
//  cout << S << " " << A << endl;

  n = S.size();
  rep(i,26) cnt[i] = 0;
  rep(i,n) cnt[S[i]-'a']++;
  rep(i,A.size()) cnt[A[i]-'a']++;

  rep(i,26) can[i] = cnt[i]/2;
  rep(i,A.size()) can[A[i]-'a']--;

  mn = 'z';
  rep(i,n){
    can[S[i]-'a']--;
    mn = min(mn, S[i]);
    if(can[S[i]-'a']<0) break;
  }

  rep(i,n) if(S[i]==mn){
    tmp = "";
    tmp += mn;
    S.erase(S.begin() + i);
    deled = 0;
    rep(k,A.size()) if(A[k]==mn){ A.erase(A.begin()+k); deled = 1; break; }
    if(deled){
      A += S.substr(0, i);
      S = S.substr(i);
      tmp += solve(S, A);
      return memo[mem] = tmp;
    }

    A += S.substr(0, i);
    S = S.substr(i);
    sort(A.begin(), A.end());
    
    rep(k,S.size()) if(S[k]==mn){
      string T = S;
      T.erase(T.begin()+k);
      tmp = mn + solve(T, A);
      if(res > tmp) res = tmp;
    }
    break;
  }

  return memo[mem] = res;
}

class FoxAndHandle {
public:
string lexSmallestName(string S) {
  memo.clear();
  return solve(S, "");
}

};

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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