SRM301Div2

250

class InsertionSortCount {
public:
  int countMoves(vector <int> A) {
    int r = 0;
    for(int i=0; i<A.size(); ++i){
      int idx = i;
      int mn = 1 << 22;
      for(int j=i; j<A.size(); ++j){
        if(mn > A[j]){
          mn = A[j];
          idx = j;
        }
      }
      if(i != idx){
        r += idx - i;
        A.erase( A.begin() + idx );
        A.insert( A.begin() + i, mn );
      }
    }
    return r;
  }
};

500
辞書順最小に作る方法が分からなかった。解説を読んだ。99ずつ引けばいいようだ。

class IndicatorMotionReverse {
public:
  int diff(char a, char b){
    string s = "-/|N";
    return (s.find(a) - s.find(b) + 4) % 4;
  }
  string itoa(int n){
    char buff[10];
    sprintf(buff, "%02d", n);
    return string( buff );
  }
  string getMinProgram(vector <string> act) {
    string r, s;
    r = s = "";
    for(int i=0; i<act.size(); ++i){
      s += act[i];
    }
    for(int i=1; i<s.size();){
      int d = diff(s[i], s[i-1]);
      int cnt = 0;
      while(i<s.size() && diff(s[i], s[i-1]) == d){
        ++cnt;
        ++i;
      }
      char c = string("SLFR")[d];
      string t = "";
      while(99 < cnt){
        t = "99" + t;
    　　t = c + t;
        cnt -= 99;
      }
      r += c + itoa(cnt) + t;
      if(100 < r.size()){
        return r.substr(0, 97) + "...";
      }
    }
    return r;
  }
};

1000
int rec(int, int, string) 内で、k+=2ではなく、++kとしていて答えが出なかった。

const int N = 50 + 1;

int t[N][N];

class CorrectingParenthesization {
public:
  int cost(char a, char b){
    if(a == '(' && b == ')')return 0;
    if(a == '{' && b == '}')return 0;
    if(a == '[' && b == ']')return 0;
    if(string("({[").find(a) != string::npos)return 1;
    if(string(")}]").find(b) != string::npos)return 1;
    return 2;
  }
  int rec(int i, int j, string s){
    if( !(i < j) )return 0;
    if(0 <= t[i][j])return t[i][j];
    int r = rec(i+1, j-1, s) + cost(s[i], s[j]);
    for(int k=i+1; k<j; k+=2){
      r = min(r, rec(i, k, s) + rec(k+1, j, s));
    }
    return t[i][j] = r;
  }
  int getMinErrors(string s) {
    fill( &t[0][0], &t[(int)s.size()][s.size()], -1 );
    return rec(0, (int)s.size()-1, s);
  }
};