Educational Codeforces Round 96

Dashboard - Educational Codeforces Round 96 (Rated for Div. 2) - Codeforces

F. Realistic Gameplay

区間の始めに余っている弾を捨ててreloadする必要はない。(余っている分を使えばいいので)したがってreloadは区間の終わりに時間の余裕があるときのみ考えればよい。

とすると状態数、遷移のDPができる。

Submission

void solve() {
  int n;
  ll k;
  cin >> n >> k;
  vector<ll> l(n), r(n), a(n);
  for (int i = 0; i < n; i++) cin >> l[i] >> r[i] >> a[i];
  vector<ll> dp(n + 1, LLINF);
  dp[0] = 0;
  for (int i = 0; i < n; i++) {
    if (dp[i] == LLINF) continue;
    ll rem = k;
    ll use = 0ll;
    for (int j = i; j <= n; j++) {
      if (j == n) {
        chmin(dp[n], dp[i] + use);
        break;
      }
      if (rem + k * (r[j] - l[j]) < a[j]) break;
      // いくら余るか
      ll tmp = rem + k * (r[j] - l[j]) - a[j];
      if (tmp > 0) tmp = (tmp - 1) % k + 1;
 
      use += a[j];
 
      dmp(i, j, rem, tmp, use);
      // 間で補充
      if (j + 1 < n && r[j] < l[j + 1]) chmin(dp[j + 1], dp[i] + use + tmp);
      // 区間の最後で補充
      if ((a[j] - rem + k - 1) / k < r[j] - l[j])
        chmin(dp[j + 1], dp[i] + use + tmp % k);
 
      rem = tmp;
    }
  }
 
  if (dp[n] == LLINF)
    cout << -1 << endl;
  else
    cout << dp[n] << endl;
 
  return;
}

G. Yet Another DAG Problem

頂点に割り当てる値は頂点数以下でよいことに着目する。(これ超本質)

とする。愚直にやるならば更新でを割り当てる頂点集合を全部みてとかになる。頂点集合にを割り当てられるかどうかは、 から到達可能な頂点全てに以下が割り当てられているかどうかで判定できる。

これでは間に合わないのでグラフがDAGであることを利用する。 を割り当てる頂点をトポロジカル順序で前のものから順に見ていくことにすれば、トポロジカル順序が後の点が前の点から到達可能であるのにもかかわらず 同時にが割り当てられるということはない。(前の点が追加された時点で、後の点は前の点から到達可能ならば以下が割り当てられているはず)

よってでこのDPができる。あとは復元すればOK。

Submission

void solve() {
  int n, m;
  cin >> n >> m;
  vector<ll> c(n, 0);
  Graph g(n);
  for (int i = 0; i < m; i++) {
    int a, b, w;
    cin >> a >> b >> w;
    a--;
    b--;
    c[a] += w;
    c[b] -= w;
    g.add_edge(a, b);
  }
  auto topo = topological_order(g);
 
  vector<int> reach(n, 0);
  for (int i = n - 1; i >= 0; i--) {
    int v = topo[i];
    for (auto e : g[v]) {
      reach[v] |= (1 << e.to);
      reach[v] |= reach[e.to];
    }
  }
 
  // dp[i][j] := jの頂点に[0, i]を割り当てるときの最小値
  auto dp = vect(n + 1, vect(1 << n, LLINF));
  auto prev = vect(n + 1, vect(1 << n, -1));
  dp[0][0] = 0;
  for (int i = 0; i < n; i++) {
    // iを割り当てる頂点をトポロジカル順に追加
    for (int k = 0; k < n; k++) {
      for (int j = 0; j < (1 << n); j++) {
        if (dp[i][j] == LLINF) continue;
        if (chmin(dp[i + 1][j], dp[i][j])) prev[i + 1][j] = j;
        int v = topo[k];
        if ((j >> v) & 1) continue;
        if ((reach[v] & j) == reach[v]) {
          if (chmin(dp[i][j | (1 << v)], dp[i][j] + c[v] * i))
            prev[i][j | (1 << v)] = prev[i][j];
        }
      }
    }
  }
 
  vector<ll> ans(n, 0);
  int S = (1 << n) - 1;
  int X = n;
  while (X > 0 && S != 0) {
    int T = prev[X][S];
    int U = S ^ T;
    for (int i = 0; i < n; i++) {
      if ((U >> i) & 1) ans[i] = X;
    }
    S = T;
    X--;
  }
  cout << ans << endl;
  return;
}