Entries

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

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

コメント

[C47]

"すでに最大長を過ぎたかどうか"というフラグは思いつきませんでした。。覚えておきます。
自分は dp[i][j]=1 or 0 (iからjまで空欄なしで連続させれるか) と
fwd[i] (最初からiまでに空欄が最低いくつあるか)
bwd[i] (iから最後までに空欄が最低いくつあるか)
を作って
if(dp[i][j]){A=j-i+1;B=fwd[i]+bwd[j];ans=max(ans,A*A-B);}
という謎実装ゲーにしてしまいました。
結果解けたのはCoding PhaseとChallenge Phaseの間というorz
  • 2010-05-13 23:01
  • mirac
  • URL
  • 編集

[C48]

mirac様も参加お疲れ様でした!
"すでに最大長を過ぎたかどうか"を状態に組み込んだ方が考え方がわかりやすいじゃん(個人的に)というのは,自分も後で考えたものです.ごめんなさい.
mirac氏のやり方も,大して手間は変わらないし,わかりやすいので良いと思いますけどねー.
時間内に解いて,無謀なチャレンジがなければ抜かれてたかな…,チャレンジあっても抜かれてるか.
  • 2010-05-14 06:48
  • rsujskf
  • URL
  • 編集

コメントの投稿

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

トラックバック

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

Open 2010 Qual. 2 HARD - HandlesSpelling (この記事を編集する[管理者用])

Source

TopCoder Open 2010 Algorithm Qualification Round 2 HARD (1000pt)
Problem Statement
TopCoderニコ生オープン 第1回 自分の参加記録

問題概要

長さ1000以下の文字列Sと,50個以下の長さ50以下の文字列A[i]が与えられる.
各A[i]はいくら使っても良くて,A[i]を並べて,Sを作りたい.
オーバーラップは許されないとして,
 X^2 - Y
でスコアリングする.
XはA[i]たちでカバーされた最長のSの部分文字列.
YはA[i]たちでカバーされなかったSの文字数.
最大スコアを求める問題.
(日本語がうまく書けないので,詳細は問題文を見てくださいorz)

解法

DP.
 dp[fg][i][j] = Sのi文字目以降を考えていて,i文字目より前は,今jだけ連続してカバーできている状態での,最高スコア
ただし,fg=1なら既に,カバーしてる長さ最大の部分文字列を過ぎた,fg=0ならまだ.
2*1000*1000の状態数だけど,fg=1ならjを考えなくて良いので,実質1000*1000+1000ぐらいの状態数.
もしくは,
 dp[st][ed] = S.substr(S.begin()+st,S.begin()+ed) でカバーできない最小の文字数
を求めて後でスコアを計算するなどでもいいかも.(たぶんこっちのほうが賢い)

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

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

#define MINF -2000000000

string in; int n, m;
int ok[1100][60], len[60];
int dp[1100], dp2[1100][1100];

int solve(int st){
  int i,k,res;

  if(dp[st]!=MINF) return dp[st];
  if(st==n) return dp[st]=0;

  res = solve(st+1) - 1;
  rep(i,m) if(ok[st][i]){
    k = solve(st+len[i]);
    if(res<k) res=k;
  }

  return dp[st]=res;
}

int solve2(int st,int con){
  int i,k,res;

  if(dp2[st][con]!=MINF) return dp2[st][con];

  res = solve(st) + con*con;
  if(st==n) return dp2[st][con]=res;

  k = solve2(st+1,0) - 1;
  if(res < k) res = k;
  rep(i,m) if(ok[st][i]){
    k = solve2(st+len[i],con+len[i]);
    if(res<k) res=k;
  }

  return dp2[st][con]=res;
}

class HandlesSpelling {
public:
int spellIt(vector <string> parts, vector <string> badges) {
  int i,j;

  in.clear();
  rep(i,parts.size()) in+=parts[i];
  n=in.size(); m=badges.size();

  rep(j,m) len[j]=badges[j].size();
  rep(i,n) rep(j,m){
    ok[i][j]=0;
    if(in.substr(i,len[j])==badges[j]) ok[i][j]=1;
  }

  rep(i,n+1) dp[i]=MINF;
  rep(i,n+1) rep(j,n+1) dp2[i][j]=MINF;

  return solve2(0,0);
}

};

以下はTopCoderニコ生Open本番中にサブミットしたコード.

// #includeとusing namespace std;は略

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

#define MINF -2000000000

vector<string> badges;
string in; int n, m;
int ok[1100][60], len[60];
int dp[1100][1100], dp2[1100][1100];

int solve(int st,int con){
  int i,j,k,res;

  if(dp[st][con]!=MINF) return dp[st][con];
  if(st==n) return dp[st][con]=0;

  res = solve(st+1,0) - 1;
  rep(i,m) if(ok[st][i]){
    k = solve(st+len[i],con+len[i]);
    if(res<k) res=k;
  }

  return dp[st][con]=res;
}

int solve2(int st,int con){
  int i,j,k,res;

  if(dp2[st][con]!=MINF) return dp2[st][con];

  res = solve(st,con) + con*con;
  if(st==n) return dp2[st][con]=res;

  k = solve2(st+1,0) - 1;
  if(res < k) res = k;
  rep(i,m) if(ok[st][i]){
    k = solve2(st+len[i],con+len[i]);
    if(res<k) res=k;
  }

  return dp2[st][con]=res;
}

class HandlesSpelling {
public:
int spellIt(vector <string> parts, vector <string> badges) {
  int i,j,k;

  in.clear();
  rep(i,parts.size()) in+=parts[i];
  n=in.size(); m=badges.size();

  rep(j,m) len[j]=badges[j].size();
  rep(i,n) rep(j,m){
    ok[i][j]=0;
    if(in.substr(i,len[j])==badges[j]) ok[i][j]=1;
  }

  rep(i,n+1) rep(j,n+1) dp[i][j]=dp2[i][j]=MINF;
  solve(0,0);

  return solve2(0,0);
}

};

コメント

[C47]

"すでに最大長を過ぎたかどうか"というフラグは思いつきませんでした。。覚えておきます。
自分は dp[i][j]=1 or 0 (iからjまで空欄なしで連続させれるか) と
fwd[i] (最初からiまでに空欄が最低いくつあるか)
bwd[i] (iから最後までに空欄が最低いくつあるか)
を作って
if(dp[i][j]){A=j-i+1;B=fwd[i]+bwd[j];ans=max(ans,A*A-B);}
という謎実装ゲーにしてしまいました。
結果解けたのはCoding PhaseとChallenge Phaseの間というorz
  • 2010-05-13 23:01
  • mirac
  • URL
  • 編集

[C48]

mirac様も参加お疲れ様でした!
"すでに最大長を過ぎたかどうか"を状態に組み込んだ方が考え方がわかりやすいじゃん(個人的に)というのは,自分も後で考えたものです.ごめんなさい.
mirac氏のやり方も,大して手間は変わらないし,わかりやすいので良いと思いますけどねー.
時間内に解いて,無謀なチャレンジがなければ抜かれてたかな…,チャレンジあっても抜かれてるか.
  • 2010-05-14 06:48
  • rsujskf
  • URL
  • 編集

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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