peryaudoのTopCoder日記

NegativeGraphDiv2

SRM626, DIV2Hard | 23:14

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>

using namespace std;
using ll = long long;

const ll INF = 1LL << 60LL;

class NegativeGraphDiv2 {
 public:
  long long findMin(int N, vector<int> s, vector<int> t, vector<int> weight, int charges) {
    vector<vector<pair<int, ll>>> edges(N);
    for (int i = 0; i < s.size(); ++i) {
      edges[s[i] - 1].emplace_back(t[i] - 1, (ll)weight[i]);
    }
    vector<vector<ll>> dist(N, vector<ll>(charges + 1, INF));
    dist[0][0] = 0;

    set<int> changed;
    changed.insert(0);

    while (!changed.empty()) {
      set<int> next_changed;
      for (int ch : changed) {
        for (int from = 0; from < N; ++from) {
          for (pair<int, ll> edge : edges[from]) {
            if (dist[edge.first][ch] > dist[from][ch] + edge.second) {
              dist[edge.first][ch] = dist[from][ch] + edge.second;
              next_changed.insert(ch);
            }
            if (ch + 1 <= charges && dist[edge.first][ch + 1] > dist[from][ch] - edge.second) {
              dist[edge.first][ch + 1] = dist[from][ch] - edge.second;
              next_changed.insert(ch);
              next_changed.insert(ch + 1);
            }
          }
        }
      }
      changed = next_changed;
    }
    return *min_element(dist.back().begin(), dist.back().end());
  }
};

基本的にはベルマンフォードするだけだが、負辺の含まれ方が特殊なので、更新されない頂点集合を大雑把にはぶいてベルマンフォードすると間に合うという問題。

FixedDiceGameDiv1

SRM626, DIV1Easy | 16:44

#include <vector>
#include <string>
#include <map>
#include <set>
#include <algorithm>
#include <iostream>
#include <cmath>
#include <climits>
#include <queue>
#include <stack>
#include <numeric>

using namespace std;

#define vector2(TYPE) vector<vector<TYPE> >
#define vector2_cons(TYPE, A, B, DEFAULT) ((A), vector<TYPE>((B), (DEFAULT)))


class FixedDiceGameDiv1 {
 public:
  vector<double> CalcPatterns(int a, int b) {
    vector2(double) dp vector2_cons(double, a + 1, 2550, 0);
    dp[0][0] = 1.0;
    for (int i = 1; i < dp.size(); ++i) {
      for (int j = 0; j < dp[0].size(); ++j) {
        for (int k = 1; k <= b; ++k) {
          if (j - k >= 0)
            dp[i][j] += dp[i - 1][j - k];
        }
      }
    }
    return dp.back();
  }

  double getExpectation(int a, int b, int c, int d) {
    double numer = 0, denomi = 0;
    vector<double> a_table = CalcPatterns(a, b);
    vector<double> b_table = CalcPatterns(c, d);
    for (int ia = 0; ia < a_table.size(); ++ia) {
      for (int jb = 0; jb < min<int>(ia, b_table.size()); ++jb) {
        numer += (double)ia * a_table[ia] * b_table[jb];
        denomi += (double)a_table[ia] * b_table[jb];
      }
    }
    if (numer == 0) return -1.0;
    return numer / denomi;
  }
};

けたあふれにちゅうい