SRM320 D1M-D2H ContestSchedule

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.

各コンテストの開始時間$s$と終了時間$e$とそのコンテストの勝利確立$p$が空白区切りで与えられる．コンテストに勝つ期待値の最大値を求める．
$$ dp[k] := 時刻kでのコンテストに勝つ期待値の最大値 $$

として動的計画法．DAGになるように，時間を昇順でソートする．時間をそのまま配列で持つと$1000000000$となりヤバイがコンテストの個数は$50$個しかないので，dpをmapで持った．コンテストの開始時間を$j$，終了時間を$k$とすると$dp[0]$$\sim$$dp[k]$での最大値から遷移すれば良いので，その最大値を$vmax$とすると$vmax + p \to$$dp[k]$となる．

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

#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;
typedef pair<P, double> PI;

map<int, double> dp;

class ContestSchedule {
  public:
  double expectedWinnings(vector <string> contests) {
      int n = contests.size();
      dp.clear();

      vector<PI> v(n);
      rep(i, n) {
          vector<int> res;
          int t = 1, x = 0;
          for(int j = contests[i].size()-1; j >= 0; j--) {
              if(contests[i][j] == ' ') {
                  res.push_back(x);
                  x = 0; t = 1;
              } else {
                  x += int(contests[i][j] - '0') * t;
                  t *= 10;
              }
          }

          res.push_back(x);

          v[i].first.first = res[2];
          v[i].first.second = res[1];
          v[i].second = res[0] / 100.0;
      }

      sort(v.begin(), v.end());

      rep(i, n) {
          int j = v[i].first.first;
          int k = v[i].first.second;
          double p = v[i].second;

          double vmax = 0.0;
          each(it, dp) {
              if(it->first <= j) vmax = max(vmax, it->second);
          }

          dp[k] = max(dp[k], vmax + p);
      }

      double ans = 0.0;
      each(it, dp) {
          ans = max(ans, it->second);
      }

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