Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

SRM461 DIV2 HARD - NameInput (この記事を編集する[管理者用])

Source

TopCoder SRM461 DIV2 HARD (1000pt)
Problem Statement

問題概要

ゲームセンターなどでプレイヤーネームを入力する感じで文字列を打ちたい.
ぐるぐる回る文字列の中には同じ文字があるかもしれない.
最小で上下に何回移動すれば良いかを求める問題.
打ちたい文字列,ぐるぐる回る文字列はそれぞれ2500文字以下.

解法

何文字目まで打ったか,ぐるぐる回る文字列のどの文字を現在選んでいるか,でメモするDP.
Aって文字を入れたいときは,上下どちらに回して一番近いAの場所に移動するかの2パターンのみを考えることで2500^2の計算量となる.
01-BFSでもOK.(ダイクストラでも解けるが計算時間が怪しいらしい)

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 INF 1000000000

class NameInput {
public:
int countUpDownKeyPresses(vector <string> predictionSequence, vector <string> name) {
  int i,j,k,st,pl,dist,n;
  int res;
  string utitai, mojiretu;
  int dp[2600],next[2600];

  rep(i,predictionSequence.size()) mojiretu+=predictionSequence[i];
  rep(i,name.size()) utitai+=name[i];
  n=mojiretu.size();

  dp[0]=0; REP(i,1,n) dp[i]=INF;
  rep(k,utitai.size()){
    rep(i,n) next[i]=INF;
    rep(i,n) if(mojiretu[i]==utitai[k]) break;
    if(i==n) return -1;

    st=i;
    rep(i,n){
      if(mojiretu[(st+i)%n]==utitai[k]) pl=(st+i)%n, dist=0;
      if(next[pl] > dp[(st+i)%n] + dist) next[pl] = dp[(st+i)%n] + dist;
      dist++;
    }
    rep(i,n){
      if(mojiretu[(st+n-i)%n]==utitai[k]) pl=(st+n-i)%n, dist=0;
      if(next[pl] > dp[(st+n-i)%n] + dist) next[pl] = dp[(st+n-i)%n] + dist;
      dist++;
    }

    rep(i,n) dp[i]=next[i];
  }

  res=INF;
  rep(i,n) if(res>dp[i]) res=dp[i];
  return res;
}

};

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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