ferinの競プロ帳

競プロについてのメモ

codeforces #433 div2 D. Jury Meeting

競技プログラミング Codeforces

問題ページ Problem - D - Codeforces

考えたこと

  • 頂点iに住んでいる人が2往復以上したほうがいいことはない
  • 日付について区間[l,l+k]で議論をすると考える
  • lより前の最も安いチケットで頂点0へ行き、l+kよりもあとの最も安いチケットで頂点0から出発する
  • 各頂点jについて ticket1[i][j] = (i以前で最も安いチケットの値段), ticket2[i][j] = (i以後で最も安いチケットの値段) みたいなのを求めたくなる
  • これがわかっていればlを全て試して最も安いものを出力すればいいだけ
  • 愚直にやるとO(nmax(d))になって当然だめ
  • lとして取りうるのは飛行機が出発する時間だけ
  • r=l+kとして取りうるのは飛行機が到着する時間だけ
  • 更新が点に対してchmin、区間和みたいなのを求めたい気持ちになる
  • セグ木を貼る
  • dp1[i] = sum(ticket1[i][j] | 0<=j<n) みたいなのとすれば O(MlogN) でdp1が求まる
  • 同様にticket2についてdp2も求まる
  • 累積minを取って全てのlについて試せばいけそう
  • オーバーフローとかm=0で散々バグらせたけど通った
    -----解説を見た-----
  • 冷静になって考えると単純に配列を持っておくだけで更新ができるのでセグ木いらない
  • 全ての頂点から出発するところまで計算しておけばあとは一点が更新されるだけなので総和の更新も簡単にできる

ソースコード

セグ木で書いたやつ

#define __USE_MINGW_ANSI_STDIO 0
#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 = 1e13;
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};

template <typename monoid>
class segmentTree {
public:
  using M = monoid;
  using T = typename M::value_type;

  int sz;
  vector<T> x;

  segmentTree(int n = 1e5) {
    sz = 1; while(sz < n) sz *= 2;
    init();
  }
  void init() { x.assign(sz*2, M::id()); }

  // [a, b)
  T query(int a, int b, int k, int l, int r) {
    if(r <= a || b <= l) return 0;
    if(a <= l && r <= b) return x[k];
    return M::f(query(a, b, 2*k+1, l, (l+r)/2),
                query(a, b, 2*k+2, (l+r)/2, r));
  }
  T query(int a, int b) {return query(a, b, 0, 0, sz);}
  // 点更新
  void update(int i, const T &val) {
    i += sz-1;
    x[i] = M::g(x[i], val);
    while(i > 0) {
      i = (i-1) / 2;
      x[i] = M::f(x[i*2+1], x[i*2+2]);
    }
  }
};

template <typename T>
struct mono {
  using value_type = T;
  static constexpr T id() {return LLINF;}
  static T f(const T &a, const T &b) { return a+b; }
  static T g(const T &a, const T &b) { return min(a, b); }
};

using segtree = segmentTree<mono<int>>;

VVI ti[2];
int dp1[1000010], dp2[1000010];
signed main(void)
{
  int n, m, k;
  cin >> n >> m >> k;
  REP(i, m) {
    int d, f, t, c;
    cin >> d >> f >> t >> c;
    if(t == 0) {
      ti[0].PB({d, f-1, c});
    } else {
      ti[1].PB({d, t-1, c});
    }
  }
  sort(ALL(ti[0]));
  sort(ALL(ti[1]));

  REP(i, 1000010) dp1[i] = dp2[i] = LLINF;

  segtree seg1(n);
  REP(i, ti[0].size()) {
    int l = ti[0][i][0] + 1;
    seg1.update(ti[0][i][1], ti[0][i][2]);
    chmin(dp1[l], seg1.query(0, n));
  }

  segtree seg2(n);
  for(int i=(int)ti[1].size()-1; i>=0; --i) {
    int r = ti[1][i][0] - 1;
    seg2.update(ti[1][i][1], ti[1][i][2]);
    chmin(dp2[r], seg2.query(0, n));
  }

  FOR(i, 1, 1000001) chmin(dp1[i], dp1[i-1]);
  for(int i=1000000; i>=0; --i) chmin(dp2[i], dp2[i+1]);

  int ans = LLINF;
  REP(l, 1000001) {
    int r = l+k-1;
    if(r > 1000000) break;
    chmin(ans, dp1[l] + dp2[r]);
  }
  if(ans == LLINF) cout << -1 << endl;
  else cout << ans << endl;

  return 0;
}

セグ木使わずに書いた版

#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 = 1e13;
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};

VVI ti[2];
int dp1[1000010], dp2[1000010];
signed main(void)
{
  int n, m, k;
  cin >> n >> m >> k;
  REP(i, m) {
    int d, f, t, c;
    cin >> d >> f >> t >> c;
    if(t == 0) {
      ti[0].PB({d, f-1, c});
    } else {
      ti[1].PB({d, t-1, c});
    }
  }
  sort(ALL(ti[0]));
  sort(ALL(ti[1]));

  REP(i, 1000010) dp1[i] = dp2[i] = LLINF;

  VI seg1(n, -1);
  int cnt = 0, sum = 0;
  REP(i, ti[0].size()) {
    if(cnt < n) {
      if(seg1[ti[0][i][1]] == -1) {
        seg1[ti[0][i][1]] = ti[0][i][2];
        cnt++;
        if(cnt == n) {
          REP(j, n) sum += seg1[j];
          chmin(dp1[ti[0][i][0]+1], sum);
        }
      } else {
        chmin(seg1[ti[0][i][1]], ti[0][i][2]);
      }
    } else {
      if(seg1[ti[0][i][1]] > ti[0][i][2]) {
        sum -= seg1[ti[0][i][1]];
        seg1[ti[0][i][1]] = ti[0][i][2];
        sum += seg1[ti[0][i][1]];
        chmin(dp1[ti[0][i][0]+1], sum);
      }
    }
  }

  VI seg2(n, -1);
  cnt = 0, sum = 0;
  for(int i=(int)ti[1].size()-1; i>=0; --i) {
    if(cnt < n) {
      if(seg2[ti[1][i][1]] == -1) {
        seg2[ti[1][i][1]] = ti[1][i][2];
        cnt++;
        if(cnt == n) {
          REP(j, n) sum += seg2[j];
          chmin(dp2[ti[1][i][0]-1], sum);
        }
      } else {
        chmin(seg2[ti[1][i][1]], ti[1][i][2]);
      }
    } else {
      if(seg2[ti[1][i][1]] > ti[1][i][2]) {
        sum -= seg2[ti[1][i][1]];
        seg2[ti[1][i][1]] = ti[1][i][2];
        sum += seg2[ti[1][i][1]];
        chmin(dp2[ti[1][i][0]-1], sum);
      }
    }
  }

  FOR(i, 1, 1000001) chmin(dp1[i], dp1[i-1]);
  for(int i=1000000; i>=0; --i) chmin(dp2[i], dp2[i+1]);

  int ans = LLINF;
  REP(l, 1000001) {
    int r = l+k-1;
    if(r > 1000000) break;
    chmin(ans, dp1[l] + dp2[r]);
  }
  if(ans == LLINF) cout << -1 << endl;
  else cout << ans << endl;

  return 0;
}