Pの競プロ記

競技プログラミングに関することを書きます。

TopCoder SRM 627 Div2 Hard : BubbleSortWithReversals

概要


数列Aが与えられる。
同じ要素が被らないように連続する要素をK回まで反転することができる。

例えば、 A = {3, 2, 1, 5, 4}, K = 2のとき、
{3, 2, 1}と{5, 4}を選んで反転させると{1, 2, 3}と{4, 5}となり、数列Aは、A = {1, 2, 3, 4, 5}となる。

この動作を行った後、バブルソートで昇順にソートさせたときの要素の交換回数を最小化する問題。

解法


※Ediorialを見て解いた。(というか学んだ。)

動的計画法で解くことができる。

まず問題文についてだが「バブルソートの交換回数」は「A[i] > A[j], i < jを満たすペアの数」と言い換えることができる。だからこのペアの数が最小値を見つける。

dpの更新式は、
dp[i番目以上の要素(i から A.size()まで)][k回以下反転をさせたとき] := A[j] > A[i], 0 <= j < iを満たすペアの最小値
となる。

例えば、A = {3, 7, 8, 2, 5}のとき、dp[3][0] = 5となる。
 A[3] = 2より、それより左にある値とのペアは(3, 2), (7, 2), (8, 2)で3通り。
 A[4] = 5より、それより左にある値とのペアは(7, 5), (8, 5)で2通り。

(うまく説明できないなぁ...)

ソースコード

class BubbleSortWithReversals {
public:

  int dp[51][51];

  int countReverse(vector<int> vi, int idx) {
    int res = 0;
    
    for(int i = idx; i < vi.size(); i++) {
      for(int j = 0; j < i; j++) {
        if(vi[j] > vi[i]) res++;
      }
    }
    
    return res;
  }

  int getMinSwaps(vector <int> A, int K) {
    int n = A.size();
    vector<int> tmp;

    memset(dp, 0, sizeof(dp));

    for(int i = n - 1; i >= 0; i--) {
      for(int k = 0; k <= K; k++) {
        tmp = vector<int>(A.begin(), A.begin() + i + 1);
        dp[i][k] = countReverse(tmp, i) + dp[i + 1][k];

        if(k) {
          for(int j = i + 1; j < n; j++) {
            tmp = vector<int>(A.begin(), A.begin() + j + 1);
            reverse(tmp.begin() + i, tmp.begin() + j + 1);
            dp[i][k] = min(dp[i][k], countReverse(tmp, i) + dp[j + 1][k - 1]);
          }
        }
      }
    }

    return dp[0][K];
  }
};