Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

SRM597 DIV1 EASY/DIV2 MEDIUM - LittleElephantAndString (この記事を編集する[管理者用])

Source

TopCoder SRM597 DIV1 EASY (250pt)
TopCoder SRM597 DIV2 MEDIUM (500pt)
Problem Statement

問題概要

アルファベッド大文字からなる文字列 $A$ と $B$ が与えられる.
1回の操作で,文字列 $A$ から任意の1文字を取り出し,$A$ の先頭にくっつけることができる.
最小で何回の操作で $A = B$ とできるかを求める問題.
不可能ならそれを指摘する.
$1 \leq |A| = |B| \leq 50$

解法

$A$ と $B$ で含まれる個数が違う文字があれば不可能.
$B$ の後ろから $k$ 文字が $A$ の部分列(部分文字列ではない)ならば,$|A| - k$ 回で可能.
そのような $k$ の最大値を全探索で探す.
部分列になっているかどうかは $B$ の後ろの $k$ 文字をgreedyに $A$ の文字と対応させていってチェックする.

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

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

class LittleElephantAndString {
public:
int getNumber(string A, string B) {
  int i, j, k, n;
  int cnt[26];

  n = A.size();
  rep(i,26) cnt[i] = 0;
  rep(i,n) cnt[A[i]-'A']--, cnt[B[i]-'A']++;
  rep(i,26) if(cnt[i]) return -1;

  for(k=n; k; k--){
    j = n - k;
    rep(i,n){
      if(j==n) continue;
      if(A[i]==B[j]) j++;
    }
    if(j==n) break;
  }

  return n - k;
}

};

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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