保存されている過去のバージョンの一覧

2014年04月13日07時01分39秒

TopCoderOpen Algorithm 2014 Round 1A MEDIUM - EllysScrabble

Source

TopCoderOpen Algorithm 2014 Round 1A MEDIUM (500pt)
Problem Statement

問題概要

$N$ 文字のアルファベット大文字からなる文字列 $S$ と，正整数 $D$ が与えられる．
$S$ を並び替えるのだが，各文字は元々文字があった場所から，距離 $D$ 以下しか移動してはいけない．
（もともと $i$ 文字目の文字は，並び替えた後に $i-D$ 文字目から $i+D$ 文字目までのどこかになければいけない）
並び替えた後の文字列として考えうるものの中で辞書順最小のものを求める問題．

解法

Greedy．
$1$ 文字目から順番に決めていく．
$k$ 文字目を決めるとき，$k-D$ 文字目から $k+D$ 文字目の中で，まだ使っていない文字のうち最小のものを割り当てる．
複数あるなら，その中で，最も左の文字を割り当てる．
ただし，$k-D$ 文字目を割り当ててないなら，問題無用で割り当てる．

C++によるスパゲッティなソースコード

// #includeなどは略しています
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

class EllysScrabble {
public:
string getMin(string letters, int maxDistance) {
  int i, j, k, n;
  string res;

  n = letters.size();
  rep(i,n){
    char c = 'Z' + 1;
    if(i-maxDistance >= 0 && letters[i-maxDistance] != '.'){
      res += letters[i-maxDistance];
      letters[i-maxDistance] = '.';
      continue;
    }
    REP(j,i-maxDistance,i+maxDistance+1) if(0 <= j && j < n){
      if(letters[j]=='.') continue;
      c = min(c, letters[j]);
    }
    res += c;
    REP(j,i-maxDistance,i+maxDistance+1) if(0 <= j && j < n) if(c==letters[j]){
      letters[j] = '.';
      break;
    }
  }


  return res;
}

}

Current time: 2024年04月19日06時05分26秒
Last modified: 2014年04月13日07時01分39秒 (by laycrs)
Tags: Competitive_Programming TopCoder TopCoderOpen TCO_Algorithm TCO_Algorithm_2014 TCO_Algorithm_2014_1A
トップページに戻る

Logged in as: unknown user (not login)

ログイン：