SRM306 D2E SortMachine D1E-D2M BifidSortMachine

TopCoder Statistics - Problem Statement

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.

ある要素を抜き出し末尾に付け加える，という操作のみで数列をソートする時最小何回で出来るか．
抜き出す順番を変えることでsort出来る($[1, 3, 4, 2]$でも$[1, 4, 3, 2]$でも先に$3$を出してから$4$を出すのは変わらない)ので，sort済みの数列から何番目まであったか(連続しない部分列)を出して，それ以外を出す順番を移動する数の一番小さい方から優先してやっていけば良い．

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

#include <iostream>
#include <sstream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <queue>
#include <map>
#include <set>

#define REP(i,k,n) for(int i=k;i<n;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define INF 1<<30
#define mp make_pair

using namespace std;
typedef long long ll;
typedef pair<int,int> P;

class SortMachine {

    public:

    int countMoves(vector <int> a) {
      int n = a.size();
      vector<int> v = a;
      sort(v.begin(), v.end());

      int j = 0;
      rep(i, n) {
          if(a[i] == v[j]) {
              j++;
          }
      }

      return n - j;
    }
};

TopCoder Statistics - Problem Statement

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.

今度は末尾だけでなく先頭にも付け加えることが出来る．これはさっきの考え方と同じで，先頭の方は逆に先頭に持ってくるものの中で大きいものからやっていけば良いので，sort済みの数列の何番目から初めて何番目まであったかを全探索して，その最小値を取る．

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

#include <iostream>
#include <sstream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <queue>
#include <map>
#include <set>

#define REP(i,k,n) for(int i=k;i<n;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define INF 1<<30
#define mp make_pair

using namespace std;
typedef long long ll;
typedef pair<int,int> P;

class BifidSortMachine {

    public:
    int countMoves(vector <int> a) {
      int n = a.size();
      vector<int> v = a;
      v.push_back(INF);
      sort(v.begin(), v.end());

      int ans = INF;
      rep(i, n) {
          int j = i, cnt = 0;
          rep(k, n) {
              if(a[k] == v[j]) {
                  cnt++;
                  j++;
              }
          }
          ans = min(ans, n - cnt);
      }

      return ans;
    }
};
Aug 25th, 2016
sort, srm, topcoder