SRM316 D1M PlacingPieces

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.

長さ$L$のボードがあり，$i$番目のピースの長さは$pieces[i]$である．最小何個のピースでボードを埋めることができるか．
まずピースの長さでsortして，ボードに埋めこない最小の長さのピースを決め打ちする．この仮定があると，この長さ以上の空きスペースがあるとまだボードにピースを埋めることができ矛盾するので，そこをチェックする．

$$ dp[i][j][k] := i番目まで見てj個使い，長さkを表せるか $$

として動的計画法．$dp[i][j][k]$がtrueの時，その次の長さを使わない場合でも長さ$k$を表せるので$dp[i+1][j][k]$に遷移．また使う場合は$dp[i+1][j+1][k+pieces[i]]$に遷移する．この$dp$で$n$個まで見て実際に$i$個使い，長さ$j$を表せる時，その一番大きい隙間に決め打ちしたピースが入らなければ良い．隙間の最大値の最小値は使っていない長さ$(L - j)$を均等に$(i+1)$(両端の端を入れる)に分ける場合になるので，この値が決め打ちの長さ未満の場合解の更新ができる．

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

#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[55][55][1005];

class PlacingPieces {
  public:
  int optimalPlacement(int L, vector <int> pieces) {
      int n = pieces.size();
      sort(pieces.begin(), pieces.end());

      int ans = n;

      rep(i, n) {
          int sum = i;
          rep(j, i + 1) sum += pieces[j];
          if(sum > L) continue;

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

      rep(t, n + 1) {
          int sum = 0;
          rep(j, t) sum += pieces[j];
          if(sum > L) break;

          memset(dp, false, sizeof(dp));

          dp[t][t][sum] = true;
          REP(i, t, n) {
              REP(j, t, n) {
                  rep(k, 1005) {
                      if(dp[i][j][k]) {
                          dp[i+1][j][k] = dp[i][j][k];
                          if(k + pieces[i] < 1005) dp[i+1][j+1][k+pieces[i]] = dp[i][j][k];
                      }
                  }
              }
          }

          rep(i, n + 1) {
              rep(j, L + 1) {
                  if(dp[n][i][j]) {
                      double res = double(L - j) / (i + 1);
                      if(res < pieces[t]) {
                          ans = min(ans, i);
                      }
                  }
              }
          }
      }

      return ans;
  }
};
Oct 26th, 2016
srm, topcoder, 動的計画法