Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

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

Source

TopCoder SRM493 DIV1 MEDIUM (450pt)
Problem Statement
SRM493 DIV1 自分の参加記録

問題概要

LEN文字 (K+1以上50以下) の文字列が与えられる.
各文字は,未確定(0)か,数字の1~Kのどれか.(Kは7以下)
未確定の文字を1~Kのどれかに置き換えて,最も近くにある同じ文字間の距離を最大化したい.
最大値を求める問題.

解法

答えの最大値は高々K.
なので,前使った文字K-1文字と,今の場所を状態としてDPすれば良い.
以下コードは,違う方針で,各文字について最後に出てきた場所を状態としてDPするコード.ただしK文字より前だとK文字前と同じとみなす.

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

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

int len, K;
int in[60];
int dp[3000000], next[3000000];

class AmoebaCode {
public:
int find(string code, int ba_ka) {
  int i,j,k,st,c,m,nx,msk;
  int now[10], pw[10], n_now[10], n_mask;
  int res;

  K = ba_ka;
  len = code.size();
  rep(i,len) in[i] = (int)(code[i]-'0') - 1;

  pw[0] = 1;
  REP(i,1,10) pw[i] = pw[i-1]*K;
  rep(i,pw[K]) dp[i] = 1;
  dp[pw[K]-1]=K;

  rep(st,len){
    rep(i,pw[K]) next[i] = 1;

    rep(i,pw[K]) if(dp[i]>1) {
      m=i; rep(j,K) now[j] = m%K, m/=K;

      rep(j,K){
        n_now[j] = now[j] + 1;
        if(n_now[j] >= K) n_now[j] = K-1;
      }
      n_mask = 0;
      for(j=K-1;j>=0;j--) n_mask = n_mask * K + n_now[j];
      
      rep(c,K) if(in[st]==c || in[st]==-1){
        nx = now[c] + 1;
        if(nx > dp[i]) nx = dp[i];

        msk = n_mask - n_now[c] * pw[c];
        if(next[msk] < nx) next[msk] = nx;
      }
    }
    rep(i,pw[K]) dp[i] = next[i];
  }

  res = 1;
  rep(i,pw[K]) if(res < dp[i]) res = dp[i];
  return res;
}

};

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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