TopCoderOpen Algorithm 2014 Round 1A EASY - EllysSortingTrimmer

Source

TopCoderOpen Algorithm 2014 Round 1A EASY (250pt)
Problem Statement

問題概要

$N$ 文字のアルファベット大文字からなる文字列 $S$ と，正整数 $L$ が与えられる．
以下の操作を何回でも繰り返すことができる．

最終的に得られる文字列として，辞書順最小のものを求める問題．

解法

後ろの方から操作を適用していくと，できるかぎり，小さい文字を前に持ってくることができるので，後ろのほうから操作を順番に適応していく．
もしくは，最初の文字は絶対使わなくてはいけないが，後は，頑張れば持ってこれる（$1$ 文字面した範囲で操作することで，小さい $L-1$ 文字を持ってこれる），とかやっても良い．

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

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

class EllysSortingTrimmer {
public:
string getMin(string S, int L) {
  int n;
  for(;;){
    n = S.size();
    sort(S.begin()+n-L, S.begin()+n);
    if(n==L) break;
    S.erase(S.begin()+n-1);
  }
  return S;
}

}

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

// #includeなどは略しています
class EllysSortingTrimmer {
public:
string getMin(string S, int L) {
  sort(S.begin()+1, S.end());
  S = S.substr(0, L);
  sort(S.begin(), S.end());
  return S;
}

}

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

Logged in as: unknown user (not login)

ログイン：