SRM306Div2

250
意外と悩んだ。

class SortMachine {
public:
  int countMoves(vector <int> a) {
    int r = 0; 
    vector<int> b = a;
    sort(b.begin(), b.end());
    int idx = 0;
    for(int i=0; i<a.size(); ++i){
      if(a[i] == b[idx])++idx;
      else ++r;
    }
    return r;
  }
}; 

500
すごく悩んだ。

class BifidSortMachine {
public:
  int countMoves(vector <int> a) {
    int r = 0;
    vector<int> b = a;
    sort(b.begin(), b.end());
    for(int i=0; i<a.size(); ++i){
      int idx = i;
      int cnt = 0;
      for(int j=0; j<a.size() && idx<a.size(); ++j){
        if(a[j] == b[idx]){
          ++idx;
          ++cnt;
        }
      }
      r = max(r, cnt);
    }
    return (int)a.size() - r;
  }
};

1000
250と500が強敵すぎて怖気づいた。読んでない。