Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

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

Source

TopCoder SRM497 DIV1 EASY (250pt)
TopCoder SRM497 DIV2 MEDIUM (500pt)
Problem Statement
SRM497 DIV1 自分の参加記録

問題概要

1~N+1の数字の置換(a[0], a[1], ..., a[N])に対して,N文字の文字列Xを
 X[k] = I (a[k+1]がa[k]より大きい)
 X[k] = D (a[k+1]がa[k]より小さい)
にて定める.
文字列が与えられるので,それに対応する置換のうち,辞書順で最小のものを求める問題.
対応するものが存在しないならそれを指摘する.
Nは50以下.

解法

基本的にはGreedy.色々な解法が考えられるので,いくつか紹介しておく.

1つ目の解法は,規則性に着目する.
最終的な答えは,1~N+1までを順番に並べたものから,Dが連続してる部分をひっくり返したものになる.
計算時間はO(N).

2つ目の解法は,再帰処理.(以下のコードの1つ目)
再帰処理で,サイズの1つ小さい,X[1]~X[N-1]の条件を満たす,a[1]~a[N]までを1~Nまでの置換として辞書順最小なものを求める.
X[0]がIならば,a[0]を1にして,X[0]がDならば,a[0]はa[1]より1だけ大きくする.
a[1]~a[N]は上下関係を保ったまま,a[0]以上なら1だけ足すことで,同じ数字をなくす.
計算時間はO(N^2).

3つ目の解法.(以下のコードの2つ目)
a[0]~a[k-1]まで決めた後,a[k]をxに出来るかどうかを全部チェックして,可能な最小のxを採用する,というのを繰り返す.
a[k]をxに出来るかどうか,というのは,その直後に連続する D (I) の数だけ,xより 小さい (大きい) 数が未使用で残っているかどうかで判定できる.
連続する D (I) の次の I (D) で,いくらでも 大きい (小さい) のに直せるので,その後は上手く配置すれば絶対に配置可能.
計算時間はO(N^3).
実際には,直後に連続するのがDの場合だけ調べれば良くて,そうなれば,残ってる数字の中から,直後に連続するDの数+1番目の数字を選べば良いことになる.
これだと,O(N^2).

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

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

class PermutationSignature {
public:
vector <int> reconstruct(string in) {
  int i; vector<int> res;

  if(in.size() == 0){
    res.push_back(1);
    return res;
  }

  res = reconstruct(in.substr(1));

  res.insert(res.begin(), 0);
  
  if(in[0]=='I') res[0] = 1;
  if(in[0]=='D') res[0] = res[1]+1;
  REP(i,1,res.size()) if(res[i] >= res[0]) res[i]++;

  return res;
}

};
// #includeとusing namespace std;は略

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

class PermutationSignature {
public:
vector <int> reconstruct(string in) {
  int i,j,k,st,n;
  int used[60]={};
  int A, B, a, b;
  vector <int> res;

  n=in.size() + 1;
  rep(i,n) res.push_back(0);

  rep(st,n) rep(k,n) if(!used[k]){
    res[st] = k+1;
    A=B=0;
    REP(i,st,n-1){
      if(i>st && in[i]!=in[i-1]) break;
      if(in[i]=='I') A++;
      if(in[i]=='D') B++;
    }
    a=b=0;
    rep(i,n) if(!used[i]){
      if(i>k) a++;
      if(i<k) b++;
    }
    if(a < A || b < B) continue;
    used[k]=1;
    break;
  }

  return res;
}

};

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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