Educational Codeforces Round 66

ぜんぶといたので

A. From Hero to Zero

解法

雑にシミュレーション

int main() {
  int T;
  cin >> T;
  while(T--) {
    int64 N, K;
    cin >> N >> K;
    int64 add = 0;
    while(N >= K) {
      add += N % K;
      N -= N % K;
      if(N != 1) {
        N /= K;
        ++add;
      }
    }
    cout << add + N << endl;
  }
}

B. Catch Overflow!

codeforces.com

解法

スタックを使った

上から見ていく

スタックの先頭に、一番内側のforの {ループの回数F, addの回数S} を持つことにすると、endがきたときに前のforにpopしてF*Sを足しこむみたいなことをする

const int64 LIM = 4294967295LL;

void fail() {
  cout << "OVERFLOW!!!" << endl;
  exit(0);
}

int main() {
  int T;
  cin >> T;

  stack< pair< int64, int64 > > st;
  st.emplace(1, 0);

  for(int i = 0; i < T; i++) {
    string S;
    cin >> S;
    if(S == "add") {
      st.top().second++;
    } else if(S == "end") {
      int64 p = 1LL * st.top().first * st.top().second;
      if(p > LIM) fail();
      st.pop();
      st.top().second += p;
      if(st.top().second > LIM) fail();
    } else {
      int x;
      cin >> x;
      st.emplace(x, 0);
    }
  }
  int64 p = 1LL * st.top().first * st.top().second;
  if(p > LIM) fail();
  cout << p << endl;
}

C. Electrification

codeforces.com

解法

${k}$ 番目の要素の値を最小化したい。

${k}$ 番目の要素の値を ${x}$ 以下にできるかどうか判定できれば、にぶたんできる。

ここで ${x}$ 以下の要素が ${k}$ 個以上あるかどうかとしても同じ。各要素について ${x}$ 以下にするためには区間 [a_i-k, a_i+k] のいずれかに設定する必要がある。

${k}$ 個以上の区間が被っている地点があれば、その位置で条件を満たすのでおわり。

void solve() {
  int N, K;
  cin >> N >> K;
  ++K;
  vector< int64 > A(N);
  cin >> A;
  int64 ok = 1LL << 40, ng = -1;

  auto check = [&](int64 D) {
    queue< int64 > L, R;
    for(int i = 0; i < N; i++) {
      L.emplace(A[i] - D);
      R.emplace(A[i] + D + 1);
    }
    int sum = 0;
    while(L.size() || R.size()) {
      if(!L.empty() && L.front() < R.front()) {
        sum++;
        if(sum >= K) return make_pair(true, L.front());
        L.pop();
      } else {
        sum--;
        R.pop();
      }
    }
    return make_pair(false, -1LL);
  };

  while(ok - ng > 1) {
    auto mid = (ok + ng) / 2;
    if(check(mid).first) ok = mid;
    else ng = mid;
  }

  cout << check(ok).second << "\n";
}


int main() {
  int T;
  cin >> T;
  while(T--) solve();
}

D. Array Splitting

codeforces.com

解法

区間 ${[ 1, n ] }$ に加えて、区間 ${[ i, n] (1 \lt i, i は distinct)}$ を ${k-1}$ 個とるときのコストと言い換えできる。

累積和してソートして上位 ${k - 1}$ 個をとるのが最適。

int main() {
  int N, K;
  cin >> N >> K;
  vector< int64 > A(N);
  cin >> A;
  reverse(begin(A), end(A));
  for(int i = 1; i < N; i++) A[i] += A[i - 1];
  int64 ret = A.back();
  A.pop_back();
  --K;
  sort(A.rbegin(), A.rend());
  for(int i = 0; i < K; i++) ret += A[i];
  cout << ret << endl;
}

E. Minimal Segment Cover

codeforces.com

解法

各地点から、それより左から始まる区間を ${1}$ 個使って行ける地点の最大値 ${pos_i}$ を求めておく。

${i}$ から ${pos_i}$ に有向辺を張ることにすると、グラフは森になっているのでたぷりんぐ

pic.twitter.com/YM6lMnOcga
— たー (@ei1333) March 30, 2019

const int SZ = 500001;

struct Doubling {
  const int LOG;

  vector< vector< int > > table;

  Doubling(int sz) : LOG(64 - __builtin_clzll(sz)) {
    table.assign(LOG, vector< int >(sz, -1));
  }

  void set_next(int k, int x) {
    table[0][k] = x;
  }

  void build() {
    for(int k = 0; k + 1 < LOG; k++) {
      for(int i = 0; i < table[k].size(); i++) {
        if(table[k][i] == -1) table[k + 1][i] = -1;
        else table[k + 1][i] = table[k][table[k][i]];
      }
    }
  }

  int lower_bound(int s, int t) {
    if(table[LOG - 1][s] < t) return -1;
    int ret = 1;
    for(int i = LOG - 1; i >= 0; i--) {
      if(table[i][s] < t) {
        s = table[i][s];
        ret += 1 << i;
      }
    }
    return ret;
  }
};


int main() {
  int N, M;
  cin >> N >> M;
  vector< int > seg(SZ, -1);
  for(int i = 0; i < N; i++) {
    int x, y;
    cin >> x >> y;
    chmax(seg[x], y);
  }
  for(int i = 1; i < SZ; i++) {
    seg[i] = max(seg[i - 1], seg[i]);
  }
  Doubling doubling(SZ);
  for(int i = 0; i < SZ; i++) {
    doubling.set_next(i, seg[i]);
  }
  doubling.build();
  while(M--) {
    int x, y;
    cin >> x >> y;
    if(seg[x] == -1) {
      cout << -1 << endl;
    } else {
      cout << doubling.lower_bound(x, y) << endl;
    }
  }
}

F. The Number of Subpermutations

codeforces.com

解法

条件を言い換えて、長さが ${x}$ かつ distinct かつ最大値が ${x}$ の区間の個数を数え上げれば良い。

各 ${i}$ について、それを左端としたときに distinct である最も右の地点までの長さ ${L_i}$ を尺取り法で求めておく。

次に長さ ${x}$ をすべて試す。長さ ${x}$ である区間には、値が ${x}$ である要素を含むので、これらの要素をすべてみていくことにする。

小さい方から試すことで、値が ${x}$ 以下からなる区間たちを効率的に管理できる（区間がマージされる回数は ${N-1}$ 回）。 ${i}$ 番目の要素が ${x}$ だとする。また、これが属する区間を [L, R] とする。

[L,i] から始まって[i, R]で終わる長さ ${x}$ のdistinctな区間の個数がわかればよくて、これは区間[max(L, i-x+1), min(R-x+1,i)]の ${L_i \ge x}$ の個数なので、データ構造を貼ると解ける。

struct UnionFindRange {
  vector< int > data;
  vector< int > left, right;

  UnionFindRange(int sz) {
    data.assign(sz, -1);
    left.resize(sz);
    right.resize(sz);
    for(int i = 0; i < sz; i++) left[i] = i;
    for(int i = 0; i < sz; i++) right[i] = i;
  }

  bool unite(int x, int y) {
    x = find(x), y = find(y);
    if(x == y) return (false);
    if(data[x] > data[y]) swap(x, y);
    left[x] = min(left[x], left[y]);
    right[x] = max(right[x], right[y]);
    data[x] += data[y];
    data[y] = x;
    return (true);
  }

  pair< int, int > range(int k) {
    k = find(k);
    return {left[k], right[k]};
  };

  int find(int k) {
    if(data[k] < 0) return (k);
    return (data[k] = find(data[k]));
  }

  int size(int k) {
    return (-data[find(k)]);
  }
};

struct SuccinctIndexableDictionary {
  size_t length;
  size_t blocks;
  vector< unsigned > bit, sum;

  SuccinctIndexableDictionary() {
  }

  SuccinctIndexableDictionary(size_t _length) {
    length = _length;
    blocks = (length + 31) >> 5;
    bit.assign(blocks, 0U);
    sum.assign(blocks, 0U);
  }

  void set(int k) {
    bit[k >> 5] |= 1U << (k & 31);
  }

  void build() {
    sum[0] = 0U;
    for(int i = 1; i < blocks; i++) {
      sum[i] = sum[i - 1] + __builtin_popcount(bit[i - 1]);
    }
  }

  bool operator[](int k) const {
    return (bool((bit[k >> 5] >> (k & 31)) & 1));
  }

  int rank(int k) {
    return (sum[k >> 5] + __builtin_popcount(bit[k >> 5] & ((1U << (k & 31)) - 1)));
  }

  int rank(bool val, int k) {
    return (val ? rank(k) : k - rank(k));
  }

  int select(bool val, int k) {
    if(k < 0 || rank(val, length) <= k) return (-1);
    int low = 0, high = length;
    while(high - low > 1) {
      int mid = (low + high) >> 1;
      if(rank(val, mid) >= k + 1) high = mid;
      else low = mid;
    }
    return (high - 1);
  }

  int select(bool val, int i, int l) {
    return select(val, i + rank(val, l));
  }
};

template< class T, int MAXLOG >
struct WaveletMatrix {
  size_t length;
  SuccinctIndexableDictionary matrix[MAXLOG];
  int zs[MAXLOG];
  int buff1[MAXLOG], buff2[MAXLOG];

  void max_dfs(int d, int l, int r, int &k, T val, vector< T > &vs) {
    if(l >= r || !k) return;
    if(d == MAXLOG) {
      while(l++ < r && k > 0) vs.push_back(val), k--;
      return;
    }
    int lc = matrix[d].rank(1, l), rc = matrix[d].rank(1, r);
    max_dfs(d + 1, lc + zs[d], rc + zs[d], k, 1ULL << (MAXLOG - d - 1) | val, vs);
    max_dfs(d + 1, l - lc, r - rc, k, val, vs);
  }

  T max_dfs(int d, int l, int r, T val, T a, T b) {
    if(r - l <= 0 || val >= b) return -1;
    if(d == MAXLOG) return val >= a ? val : -1;
    int lc = matrix[d].rank(1, l), rc = matrix[d].rank(1, r);
    T ret = max_dfs(d + 1, lc + zs[d], rc + zs[d], 1ULL << (MAXLOG - d - 1) | val, a, b);
    if(~ret) return ret;
    return max_dfs(d + 1, l - lc, r - rc, val, a, b);
  }

  int freq_dfs(int d, int l, int r, T val, T a, T b) {
    if(l == r) return 0;
    if(d == MAXLOG) return (a <= val && val < b) ? r - l : 0;
    T nv = 1ULL << (MAXLOG - d - 1) | val, nnv = ((1ULL << (MAXLOG - d - 1)) - 1) | nv;
    if(nnv < a || b <= val) return 0;
    if(a <= val && nnv < b) return r - l;
    int lc = matrix[d].rank(1, l), rc = matrix[d].rank(1, r);
    return freq_dfs(d + 1, l - lc, r - rc, val, a, b) +
           freq_dfs(d + 1, lc + zs[d], rc + zs[d], nv, a, b);
  }

  void list_dfs(int d, int l, int r, T val, T a, T b, vector< pair< T, int>> &vs) {
    if(val >= b || r - l <= 0) return;
    if(d == MAXLOG) {
      if(a <= val) vs.push_back(make_pair(val, r - l));
      return;
    }
    T nv = val | (1LL << (MAXLOG - d - 1)), nnv = nv | (((1LL << (MAXLOG - d - 1)) - 1));
    if(nnv < a) return;
    int lc = matrix[d].rank(1, l), rc = matrix[d].rank(1, r);
    list_dfs(d + 1, l - lc, r - rc, val, a, b, vs);
    list_dfs(d + 1, lc + zs[d], rc + zs[d], nv, a, b, vs);
  }


  WaveletMatrix(vector< T > data) {
    length = data.size();
    vector< T > l(length), r(length);
    for(int depth = 0; depth < MAXLOG; depth++) {
      matrix[depth] = SuccinctIndexableDictionary(length + 1);
      int left = 0, right = 0;
      for(int i = 0; i < length; i++) {
        bool k = (data[i] >> (MAXLOG - depth - 1)) & 1;
        if(k) r[right++] = data[i], matrix[depth].set(i);
        else l[left++] = data[i];
      }
      zs[depth] = left;
      matrix[depth].build();
      swap(l, data);
      for(int i = 0; i < right; i++) data[left + i] = r[i];
    }
  }

  T access(int k) {
    int ret = 0;
    bool bit;
    for(int depth = 0; depth < MAXLOG; depth++) {
      bit = matrix[depth][k];
      ret = (ret << 1) | bit;
      k = matrix[depth].rank(bit, k) + zs[depth] * bit;
    }
    return (ret);
  }

  int rank(T val, int k) {
    int l = 0, r = k;
    for(int depth = 0; depth < MAXLOG; depth++) {
      buff1[depth] = l, buff2[depth] = r;
      bool bit = (val >> (MAXLOG - depth - 1)) & 1;
      l = matrix[depth].rank(bit, l) + zs[depth] * bit;
      r = matrix[depth].rank(bit, r) + zs[depth] * bit;
    }
    return (r - l);
  }

  int select(T val, int kth) {
    rank(val, length);
    for(int depth = MAXLOG - 1; depth >= 0; depth--) {
      bool bit = (val >> (MAXLOG - depth - 1)) & 1;
      kth = matrix[depth].select(bit, kth, buff1[depth]);
      if(kth >= buff2[depth] || kth < 0) return (-1);
      kth -= buff1[depth];
    }
    return (kth);
  }

  int select(T val, int k, int l) {
    return (select(val, k + rank(val, l)));
  }


  int quantile(int left, int right, int kth) {
    if(right - left <= kth || kth < 0) return (-1);
    T ret = 0;
    for(int depth = 0; depth < MAXLOG; depth++) {
      int l = matrix[depth].rank(1, left);
      int r = matrix[depth].rank(1, right);
      if(r - l > kth) {
        left = l + zs[depth];
        right = r + zs[depth];
        ret |= 1ULL << (MAXLOG - depth - 1);
      } else {
        kth -= r - l;
        left -= l;
        right -= r;
      }
    }
    return (ret);
  }

  vector< T > topk(int l, int r, int k) {
    if(r - l < k) k = r - l;
    if(k < 0) return (vector< T >());
    vector< T > ret;
    max_dfs(0, l, r, k, 0, ret);
    return (ret);
  }

  vector< pair< T, int > > freq_list(int l, int r, T a, T b) {
    vector< pair< T, int > > ret;
    list_dfs(0, l, r, 0, a, b, ret);
    return (ret);
  }

  vector< pair< int, T > > get_rect(int l, int r, T a, T b) {
    vector< pair< T, int > > res = freq_list(l, r, a, b);
    vector< pair< int, T > > ret;
    for(auto &e : res) {
      for(int i = 0; i < e.second; i++) {
        ret.emplace_back(select(e.first, i, l), e.first);
      }
    }
    return (ret);
  }

  int rangefreq(int left, int right, T lower, T upper) {
    return (freq_dfs(0, left, right, 0, lower, upper));
  }
};


int main() {
  int N;
  cin >> N;
  vector< int > A(N);
  cin >> A;
  vector< int > belong[303030];
  for(int i = 0; i < N; i++) {
    belong[A[i]].emplace_back(i);
  }

  vector< int > add(N + 1);
  vector< int > pos(N);
  int ptr = 0;
  for(int i = 0; i < N; i++) {
    while(ptr < N && add[A[ptr]] == 0) add[A[ptr++]]++;
    pos[i] = ptr - i;
    add[A[i]]--;
  }


  WaveletMatrix< int, 20 > mat(pos);

  UnionFindRange uf(N);
  vector< int > used(N);
  int64 ret = 0;
  for(int i = 1; i <= N; i++) {
    for(auto &j : belong[i]) {
      if(j && used[j - 1]) uf.unite(j, j - 1);
      if(j + 1 < N && used[j + 1]) uf.unite(j, j + 1);
      auto range = uf.range(j);
      int L = max(range.first, j - i + 1);
      int R = min(j, range.second - i + 1) + 1;
      if(L < R) ret += mat.rangefreq(L, R, i, N + 1);
      used[j] = true;
    }
  }

  cout << ret << endl;
}

G. Yet Another Partiton Problem

codeforces.com

解法

普通にDPをすると dp[k][idx] := 区間 [1,idx]をk個に分割するときの最小コストになるが、TLEするので高速化をする。

これは分割統治でできる。区間[l,m]内だけ、あるいは[m+1,r]だけで遷移するDPの計算は再帰的にすることにすると、[l,m]から[m+1,r]に遷移する計算だけをすればよい。

i≦mのとき
mx[i]:= 区間[i+1,m]のA[idx]のmax

i>mのとき
mx[i]:= 区間[m+1,i]のA[idx]のmax

とする。これは普通にみればできる。

すると遷移はl≦i≦m, m<j≦rで以下の通りになる。

dp[k][j] = min(dp[k-1][i]+(j-i)*max(mx[i],mx[j]))

mx[i]とmx[j]のどちらが大きいかで場合分けすると嬉しそうだなあという気持ちになる。まず mx[i] のほうが大きい場合は

dp[k][j] = min(dp[k-1][i]+(j-i)*mx[i]) = min((dp[k-1][i] - i*mx[i]) + j*mx[i])

で、mx[i]を傾きとする一次関数になるのでCHTを使う。mx[j]の大きい順にjを見ていくことにすると、mx[i]がmx[j]よりも大きいものを尺取りっぽくCHTに追加していく処理をすることで効率的に最小値を求められる。

mx[j] の方が大きい場合は

dp[k][j] = min(dp[k-1][i]+(j-i)*mx[j]) = min(dp[k-1][i] - i*mx[j]) + j*mx[j]

で、これもやはりiを傾きとする一次関数になるのでCHTでできる。

CHTの追加とクエリは単調なので、全体の計算量は ${O(NK \log N)}$ 。

template< typename T, bool isMin >
struct ConvexHullTrick {
#define F first
#define S second
  using P = pair< T, T >;
  deque< P > H;

  bool empty() const { return H.empty(); }

  void clear() { H.clear(); }

  inline int sgn(T x) { return x == 0 ? 0 : (x < 0 ? -1 : 1); }

  using D = long double;

  inline bool check(const P &a, const P &b, const P &c) {
    if(b.S == a.S || c.S == b.S)
      return sgn(b.F - a.F) * sgn(c.S - b.S) >= sgn(c.F - b.F) * sgn(b.S - a.S);

    //return (b.F-a.F)*(c.S-b.S) >= (b.S-a.S)*(c.F-b.F);
    return
        D(b.F - a.F) * sgn(c.S - b.S) / D(abs(b.S - a.S)) >=
        D(c.F - b.F) * sgn(b.S - a.S) / D(abs(c.S - b.S));
  }

  void addLine(T m, T b) {
    if(!isMin) m *= -1, b *= -1;
    P line(m, b);
    if(empty()) {
      H.emplace_front(line);
      return;
    }
    if(H.front().F <= m) {
      if(H.front().F == m) {
        if(H.front().S <= b) return;
        H.pop_front();
      }
      while(H.size() >= 2 && check(line, H.front(), H[1])) H.pop_front();
      H.emplace_front(line);
    } else {
      assert(m <= H.back().F);
      if(H.back().F == m) {
        if(H.back().S <= b) return;
        H.pop_back();
      }
      while(H.size() >= 2 && check(H[H.size() - 2], H.back(), line)) H.pop_back();
      H.emplace_back(line);
    }
  }

  inline T getY(const P &a, const T &x) {
    return a.F * x + a.S;
  }

  T query(T x) {
    assert(!empty());
    int l = -1, r = H.size() - 1;
    while(l + 1 < r) {
      int m = (l + r) >> 1;
      if(getY(H[m], x) >= getY(H[m + 1], x)) l = m;
      else r = m;
    }
    if(isMin) return getY(H[r], x);
    return -getY(H[r], x);
  }

  T queryMonotoneInc(T x) {
    assert(!empty());
    while(H.size() >= 2 && getY(H.front(), x) >= getY(H[1], x)) H.pop_front();
    if(isMin) return getY(H.front(), x);
    return -getY(H.front(), x);
  }

  T queryMonotoneDec(T x) {
    assert(!empty());
    while(H.size() >= 2 && getY(H.back(), x) >= getY(H[H.size() - 2], x)) H.pop_back();
    if(isMin) return getY(H.back(), x);
    return -getY(H.back(), x);
  }

#undef F
#undef S
};

int main() {
  int N, K;
  cin >> N >> K;
  vector< int > A(N);
  cin >> A;


  auto dp = make_v< int >(K, N);
  fill_v(dp, inf);
  {
    int mx = 0;
    for(int i = 0; i < N; i++) {
      chmax(mx, A[i]);
      dp[0][i] = (i + 1) * mx;
    }
  }

  vector< int > mx(N);
  ConvexHullTrick< int64, true > cht;
  function< void(int, int) > rec = [&](int l, int r) {
    if(l >= r) return;
    int mid = (l + r) / 2;
    rec(l, mid);

    {
      int tap = 0;
      for(int i = mid; i >= l; i--) {
        mx[i] = tap;
        chmax(tap, A[i]);
      }
    }

    {
      int tap = 0;
      for(int i = mid + 1; i <= r; i++) {
        chmax(tap, A[i]);
        mx[i] = tap;
      }
    }

    for(int i = 1; i < K; i++) {
      int ptr = mid;
      for(int k = mid + 1; k <= r; k++) {
        while(ptr >= l && mx[ptr] <= mx[k]) {
          cht.addLine(-ptr, dp[i - 1][ptr]);
          --ptr;
        }
        if(ptr != mid) chmin(dp[i][k], cht.queryMonotoneInc(mx[k]) + k * mx[k]);
      }
      cht.clear();
    }


    for(int i = 1; i < K; i++) {
      int ptr = l;
      for(int k = r; k > mid; k--) {
        while(ptr <= mid && mx[ptr] > mx[k]) {
          cht.addLine(mx[ptr], dp[i - 1][ptr] - ptr * mx[ptr]);
          ++ptr;
        }
        if(ptr != l) chmin(dp[i][k], cht.queryMonotoneDec(k));
      }
      cht.clear();
    }


    rec(mid + 1, r);
  };
  rec(0, N - 1);
  cout << dp[K - 1][N - 1] << endl;
}

ei1333の日記

ぺこい

Educational Codeforces Round 66

A. From Hero to Zero

解法

B. Catch Overflow!

解法

C. Electrification

解法

D. Array Splitting

解法

E. Minimal Segment Cover

解法

F. The Number of Subpermutations

解法

G. Yet Another Partiton Problem

解法