Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

SRM490 DIV1 MEDIUM - QuickT9 (この記事を編集する[管理者用])

Source

TopCoder SRM490 DIV1 MEDIUM (550pt)
Problem Statement
SRM490 DIV1 自分の参加記録

問題概要

高々1300個程度の単語のリストと,携帯で打ちたい文字列 (長さは最大で50) が与えられる.
文字列を打つために押さなければならないキーの最小値を求める問題.
アルファベットはそれぞれ数字に対応しており(違うアルファベットが同じ数字に対応していることがある),
登録されている単語の最初とマッチする辞書順で最小の文字列が表示される.
辞書順で次の文字列を表示するには1キーかかり,決定にも1キーかかる.
決定と同時に,最後の1文字消去するのは,決定だけと同じキー数ででき,それ以降最後の1文字消すのには1キーかかる.
ルールの詳細,厳密な定義は問題文を参照のこと.

解法

最初に,各単語の頭からk文字を入力するためにはキーを何回押さないといけないというのを求めた後,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)

char *key[]={
  "",
  "",
  "abc",
  "def",
  "ghi",
  "jkl",
  "mno",
  "pqrs",
  "tuv",
  "wxyz"
};

#define INF 1000000000

vector<string> go; string in;
int cost[2000][60];
int dp[60];

int solve(int st){
  int i,j,k,res=INF;
  int add, tmp;

  if(dp[st]>=0) return dp[st];
  if(st==in.size()) return dp[st]=0;

  rep(k,go.size()){
    rep(i,go[k].size()){
      if(st+i+1 > in.size()) break;

      add = cost[k][i];

      if(in[st+i]!=go[k][i]) break;
      tmp = solve(st+i+1) + add;
      if(res > tmp) res = tmp;
    }
  }

  return dp[st]=res;
}

class QuickT9 {
public:
int minimumPressings(vector <string> baka, string word) {
  int i,j,k,a,b;
  int res;
  int is_same[26][26];
  int ok[2000], tmp;
  vector<string> t9;

  rep(i,26) rep(j,26) is_same[i][j]=0;
  REP(i,2,10){
    for(k=0;;k++) if(key[i][k]<' ') break;
    rep(a,k) rep(b,k) is_same[key[i][a]-'a'][key[i][b]-'a']=1;
  }

  rep(i,baka.size()){
    string add="";
    baka[i] += " ";
    rep(k,baka[i].size()){
      if(baka[i][k]==' '){ if(add!="") t9.push_back(add); add=""; }
      else add += baka[i][k];
    }
  }

  sort(t9.begin(), t9.end());
  rep(k,t9.size()) rep(a,t9[k].size()) cost[k][a] = INF;
  rep(k,t9.size()){
    rep(i,t9.size()) ok[i]=1;
    rep(a,t9[k].size()){
      rep(i,t9.size()) if(ok[i]){
        if(a >= t9[i].size()){ok[i]=0; continue;}
        if(is_same[t9[i][a]-'a'][t9[k][a]-'a']==0){ok[i]=0; continue;}
      }
      tmp = a+2;
      {
        set<string> s;
        rep(i,k+1) if(ok[i]) s.insert(t9[i].substr(0,a+1));
        tmp += s.size()-1;
      }
      cost[k][a] = tmp;
      rep(b,a) if(cost[k][a-b-1] > cost[k][a]+b) cost[k][a-b-1] = cost[k][a]+b;
    }
  }
  
//  rep(i,t9.size()) rep(j,t9[i].size()) cout << t9[i].substr(0,j+1) << " " << cost[i][j]<

  go = t9; in = word;
  rep(i,60) dp[i] = -1;
  res = solve(0);

  if(res>=INF) res=-1;
  return res;
}

};

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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