SRM309 D1M KMonotonic

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.

数列を$K$個に分けた時に，それぞれの数列に狭義での単調増加数列か，単調減少数列にしたい．要素の値を$1$変更するには$1$コストがかかる時，その最小コストを求める．

区間$[l, r)$を単調増加，単調減少の数列にする最小コストがわかれば，後はどこで区切るか，何回区切るかを持ってメモ化再起すれば良いと分かったが，区間$[l, r)$の最小の出し方が分からなかった．解説を見てしまった．

TopCoder SRM 309 Div1 Medium KMonotonic - simezi_tanの日記

問題 n本の相異なる直線が与えられる。 n本の直線の集合の、点対称の中心の個数を求めよ。 無限にある場合..

単純に区間$[l, r)$だけを状態として持つわけではなく右端の値も持って

$$ dp[l][r][k] := [l, r)の右端の値をk変更した時の最小値 $$

として動的計画法をした．この$k$変更するという範囲は$-n \sim n$までやっておけば大丈夫という勘違いをして，単調増加の場合には

1
2
3
4
5
6
7
8
9
10
11
12
13
14

rep(i, n) {
  REP(j, i + 1, n) {
      REP(k, -n, n) {
          REP(l, -n, n) {
              int a = sequence[j-1] + k;
              int b = sequence[j] + l;

              if(a < b) {
                  dp[i][j+1][l] = min(dp[i][j+1][l], dp[i][j][k] + abs(sequence[j] - l));
              }
          }
      }
  }
}

としていた．これでは$[0, 10000, 0]$といったようなケースには対応出来ないため，変化させるのは各要素に$-n \sim n$足したものを候補としなければならない．となると$n$個の要素に対して$-n \sim n$足した$2n ^2$個の候補が出来るため，上の方法では計算量が$n ^6$となってしまい間に合わない．$[l, r)$の右端が$k(index)$の時，単調増加数列になっているという時は$[l, r-1)$の右端が$k$より小さければ何でも良いので，一番小さいものからの遷移で大丈夫ということが分かる．

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

rep(i, n) {
  int res = INF;
  rep(j, m) {
      res = min(res, abs(sequence[i] - v[j])); //それより以前にコストが少ないものがあればそれで良い
      dp[i][i+1][j] = res;
  }
}

rep(i, n) {
  REP(j, i + 1, n) {
      REP(k, 1, m) {
          dp[i][j+1][k] = min(dp[i][j+1][k], dp[i][j][k-1] + abs(sequence[j] - v[k])); //[l, r-1)の右端がv[k]より小さい時の最適コスト + jをv[k]に変えるコスト
          dp[i][j+1][k] = min(dp[i][j+1][k], dp[i][j+1][k-1]); // 以前より小さいものがあればそれを採用
      }
  }
}

後は区間$[l, r)$の最小コストは$k$に対してループを回した時の最小値となる．単調減少の場合は，候補のvectorをひっくり返して同じことをやった．これが出ると，あとは再起で区間$[l, r)$を残り$k$回分解しなければならない時の最小値として，区切る場所を全て試した．メモリが厳しくて適当に配列を取ったたらMLEした．

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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118

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

#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;

int dp[50][51][50*51*2], up[55][55], down[55][55];

// int memo[50][51][50*51*2];

int dfs(int l, int r, int k) {
  if(dp[l][r][k] != -1) return dp[l][r][k];
  if(k == 1) return min(up[l][r], down[l][r]);

  int ret = INF;
  REP(i, l + 1, r) {
      ret = min(ret, dfs(l, i, 1) + dfs(i, r, k - 1));
  }

  return dp[l][r][k] = ret;
}

class KMonotonic {
  public:
  int transform(vector <int> sequence, int K) {
      int n = sequence.size();
      vector<int> v;
      rep(i, n) {
          REP(j, -n, n + 1) v.push_back(sequence[i] + j);
      }
      sort(v.begin(), v.end());
      v.erase(unique(v.begin(),v.end()),v.end());
      int m = v.size();

      {
          rep(i, 50) rep(j, 51) {
              up[i][j] = INF;
              rep(k, 50 * 51 * 2) dp[i][j][k] = INF;
          }

          rep(i, n) {
              int res = INF;
              rep(j, m) {
                  res = min(res, abs(sequence[i] - v[j]));
                  dp[i][i+1][j] = res;
              }
          }

          rep(i, n) {
              REP(j, i + 1, n) {
                  REP(k, 1, m) {
                      dp[i][j+1][k] = min(dp[i][j+1][k], dp[i][j][k-1] + abs(sequence[j] - v[k]));
                      dp[i][j+1][k] = min(dp[i][j+1][k], dp[i][j+1][k-1]);
                  }
              }
          }

          rep(i, n) {
              REP(j, i + 1, n + 1) {
                  rep(k, m) {
                      up[i][j] = min(up[i][j], dp[i][j][k]);
                  }
              }
          }
      }
      {
          reverse(v.begin(), v.end());
          rep(i, 50) rep(j, 51) {
              down[i][j] = INF;
              rep(k, 50 * 51 * 2) dp[i][j][k] = INF;
          }

          rep(i, n) {
              int res = INF;
              rep(j, m) {
                  res = min(res, abs(sequence[i] - v[j]));
                  dp[i][i+1][j] = res;
              }
          }

          rep(i, n) {
              REP(j, i + 1, n) {
                  REP(k, 1, m) {
                      dp[i][j+1][k] = min(dp[i][j+1][k], dp[i][j][k-1] + abs(sequence[j] - v[k]));
                      dp[i][j+1][k] = min(dp[i][j+1][k], dp[i][j+1][k-1]);
                  }
              }
          }
          
          rep(i, n) {
              REP(j, i + 1, n + 1) {
                  rep(k, m) {
                      down[i][j] = min(down[i][j], dp[i][j][k]);
                  }
              }
          }
      }

      rep(i, n) rep(j, n + 1) rep(k, m) dp[i][j][k] = -1;
      int ret = dfs(0, n, K);
      return ret;
  }

};
Sep 3rd, 2016
srm, topcoder, 動的計画法, 区間dp, 数列