ferinの競プロ帳

競プロについてのメモ

Codeforces Round #185 (Div. 1) B. Cats Transport

問題ページ Problem - B - Codeforces

{}

解法

猫が止まる時間や丘までの距離など色々あって扱いにくいのでまずは処理しやすいように言い換える。丘に到達してから猫が待つ時間は猫と飼育員が丘0を出発する時間の差に等しい。したがって各猫が丘0を出発する時間がわかっていればこの時間との差だけを考えればいいので丘の距離などを考える必要がなくなった。t[i] = (猫iが丘0を出発した時間) として数列tはソートしたものとする。

dp[i][j] = (i人の飼育家が猫jに合わせて出発したときの待ち時間の合計の最小) としてDPをすることを考える。 \begin{align} dp[i][j] = {\rm min}_{k<j} \{dp[i-1][k] + (猫k+1から猫jを待たせる時間)\} \end{align} \begin{align} dp[i][j] = {\rm min}_{k<j} \{dp[i-1][k] + \sum_{l=k+1}^{j} (t[j]-t[l])\} \end{align} \begin{align} dp[i][j] = {\rm min}_{k<j} \{dp[i-1][k] + (j-k)t[j] - \sum_{l=k+1}^{j} t[l]\} \end{align} 数列の区間和を累積和で表す。Tを数列tの累積和を取ったものとすると、 \begin{align} dp[i][j] = {\rm min}_{k<j} \{dp[i-1][k] + (j-k)t[j] - (T[j] - T[k])\} \end{align} dp[i][j] = min_{k<j} {-kt[j] + dp[i-1][k] + T[k]} + jt[j] - T[j]
(最後の行だけどうがんばっても数式が反映されなかったのでこうなりました)
ここでminの中に注目すると傾き-k、切片dp[i-1][k]+T[k]の直線でx=t[j]のときのminを求めていることに等しい。したがってconvexHullTrickを用いることができO(PM)で解くことができた。傾きには単調性がありt[j]にも単調性があるので二分探索などを使う必要はない。

公式editorialが理解不能で無限に時間を溶かしてしまった

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
#define int ll
using VI = vector<int>;
using VVI = vector<VI>;
using PII = pair<int, int>;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define PB push_back

const ll LLINF = (1LL<<60);
const int INF = (1LL<<30);
const int MOD = 1000000007;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template <typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; }
template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); }
template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
  out<<'('<<a.first<<','<<a.second<<')';
  return out;
}
template<class T>
ostream &operator <<(ostream& out,const vector<T>& a){
  out<<'[';
  REP(i, a.size()) {out<<a[i];if(i!=a.size()-1)out<<',';}
  out<<']';
  return out;
}

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

// 直線の傾きに単調性があるときのCHT O(n)
// 最大なら <= になる
class ConvexHullTrick {
public:
  deque<PII> que;
  // ax + b を追加
  void add(int a, int b) {
    PII p(a, b);
    while(que.size() >= 2 && check(que[que.size()-2], que.back(), p)) {
      que.pop_back();
    }
    que.PB(p);
  }
  // 単調性がある xの位置での最小のy
  int incl_query(int x) {
    assert(que.size());
    while(que.size() >= 2 && f(que[0],x) >= f(que[1],x)) {
      que.pop_front();
    }
    return f(que[0], x);
  }
  // 単調性なし
  int query(int x) {
    int lb = -1, ub = que.size()-2;
    while(ub-lb > 1) {
      int mid = (lb+ub)/2;
      if(isright(que[mid], que[mid+1], x)) lb = mid;
      else ub = mid;
    }
    return f(que[ub], x);
  }

  bool isright(const PII &p1, const PII &p2, int x) {
    return (p1.second-p2.second) >= x * (p2.first-p1.first);
  }
  bool check(const PII &a, const PII &b, const PII &c) {
    return (b.first-a.first)*(c.second-b.second)>=(b.second-a.second)*(c.first-b.first);
  }
  int f(const PII &p, int x) { return p.first * x + p.second; }
};
ConvexHullTrick cht;

int d[100010], t[100010], T[100010], dp[105][100010];
signed main(void)
{
  int n, m, p;
  cin >> n >> m >> p;
  REP(i, n-1) cin >> d[i+1];
  REP(i, n-1) d[i+1] += d[i];
  REP(i, m) {
    int a, b;
    cin >> a >> b;
    t[i] = (b-d[a-1]);
  }
  sort(t, t+m);
  T[0] = t[0];
  REP(i, m-1) T[i+1] += T[i] + t[i+1];

  REP(i, m) dp[0][i] = (i+1)*t[i] - T[i];
  FOR(i, 1, p) {
    cht.que.clear();
    dp[i][0] = t[0] - T[0];
    cht.add(0, dp[i-1][0] + T[0]);
    FOR(j, 1, m) {
      dp[i][j] = cht.incl_query(t[j]) + t[j]*j - T[j];
      cht.add(-j, dp[i-1][j] + T[j]);
    }
  }

  cout << dp[p-1][m-1] << endl;

  return 0;
}