Codeforces Round #433 (Div. 1, based on Olympiad of Metropolises)

人生が開始した.

2179->2301(+122)
黄色になりました！！(1個色を飛び越えた... pic.twitter.com/Q2jQO178NS
— うし (@ei1333) 2017年9月6日

oooo- 3480pts 41st. なんで僕こどふぉで4完できるんや.

A. Planning

問題概要

${n(1 \le n \le 3 \times 10^5)}$ 個の飛行機が ${k + 1(k \le n)}$ 分から ${k + n}$ 分の間に ${1}$ 分ごとに出発する. ただし ${i}$ 番目の飛行機は出発予定時刻の ${i}$ 分以降に出発する必要がある.

${i}$ 番目の飛行機は出発予定時刻から ${1}$ 分遅れるごとにコスト ${c_i(1 \le c_i \le 10^7)}$ かかる. 全ての飛行機を最適な順序で出発させたときの合計最小コストと, そのときのそれぞれの飛行機の出発時刻を求めよ.

解法

${k + 1}$ 分に出発する飛行機から順に決定していく. コストを最小にするためには任意のアの瞬間において, なるべく大きい ${c_i}$ の飛行機を先に使うのが最適. ただし現在時刻を ${x}$ とすると ${x - i \ge k}$ を満たす必要がある.

条件を満たした飛行機を候補に順次追加するようにすれば, その中から ${c_i}$ の最大のものを取り出す問題に帰着できる. これは優先度つきキューでできるためえい.

${O(n \log n)}$ .

ソース

個人的にはこの問題が一番難しかった(ア. あまりに解けないので不参加を考えた.

貪欲難しい.

#include <bits/stdc++.h>

using namespace std;

typedef long long int64;

int main()
{
  int N, K, C[300000];

  int ans[300000];

  scanf("%d %d", &N, &K);
  for(int i = 0; i < N; i++) scanf("%d", &C[i]);

  priority_queue< pair< int, int > > st;
  for(int i = 0; i < K; i++) st.emplace(C[i], i);
  
  int64 ret = 0LL;
  for(int i = K; i < N + K; i++) {
    if(i < N) st.emplace(C[i], i);
    auto p = st.top();
    st.pop();
    ret += 1LL * p.first * (i - p.second);
    ans[p.second] = i;
  }

  printf("%lld\n", ret);
  for(int i = 0; i < N; i++) printf("%d ", ans[i] + 1);
  puts("");
}

B. Jury Meeting

codeforces.com

問題概要

${0}$ から ${n(1 \le n \le 10^5)}$ の ${n + 1}$ 個の街があって, 街 ${1}$ から ${n}$ に住む ${n}$ 人が, あるタイミングで街 ${0}$ に ${k(1 \le k \le 10^6)}$ 日間集まり, 最終的にもといた街に帰る必要がある.

${m(0 \le m \le 10^5)}$ 個のフライトがあって, ${i}$ 番目の飛行機は ${d_i(1 \le d_i \le 10^6)}$ 日目に街 ${f_i(0 \le f_i \le n)}$ から街 ${t_i(0 \le t_i \le n)}$ にコスト ${c_i(1 \le c_i \le 10^6)}$ で移動できる. ただし ${f_i}$ か ${t_i}$ のどちらか一方は必ず ${0}$ を満たす.

それぞれは街 ${0}$ の到着日と出発日を除いた日に集まることが可能である. 合計最小コストを求めよ.

解法

${i}$ 日目から ${k}$ 日間集まるためには, それ以前に全員が街 ${0}$ に到着していて, ${i + k}$ 日目より後に全員がもとの街に戻る必要がある.

ぐっと睨むと前者と後者は独立で ${\mathrm{dp1}[j] :=}$ ${j}$ 日目以前に全員が街 ${0}$ に到着するための最小コスト, ${\mathrm{dp2}[j] :=}$ ${j}$ 日目以降で全員がもとの街に戻るための最小コストが求まれば, あとは適当に足し合わせて最小をとればよい. で, 後者は前者を反転させた問題なので, 前者が解ければ後者も解ける.

この問題は左から見ていくとできる(できるので). 補助用のアとして ${\mathrm{member}[i] := }$ 街 ${i}$ の人が街 ${0}$ に来るための現在の最小コストを持っておく. すると右に ${1}$ 日ずらす更新が, 変化したところだけみれば素早くできるためはいになる.

ソース

こういうのは得意っぽい.

#include <bits/stdc++.h>

using namespace std;

typedef long long int64;
const int64 INF = 1LL << 59;

int N, M, K, D[100000], F[100000], T[100000], C[100000];
vector< pair< int, int > > in[1000005], out[1000005];
int64 dp1[1000005], dp2[1000005], member[100005];

int main()
{
  scanf("%d %d %d", &N, &M, &K);
  for(int i = 0; i < M; i++) {
    scanf("%d %d %d %d", &D[i], &F[i], &T[i], &C[i]);
    if(T[i] == 0) in[D[i]].emplace_back(F[i], C[i]);
    else out[D[i]].emplace_back(T[i], C[i]);
  }

  {
    int64 rest = N, cost = 0;
    fill_n(dp1, 1000005, INF);
    fill_n(member, 100005, INF);
    for(int i = 0; i < 1000005; i++) { // begin date
      if(rest == 0) {
        dp1[i] = cost;
      }

      for(auto &s : in[i]) {
        if(member[s.first] == INF) {
          --rest;
          member[s.first] = s.second;
          cost += s.second;
        } else if(s.second < member[s.first]) {
          cost -= member[s.first];
          member[s.first] = s.second;
          cost += member[s.first];
        }
      }
    }
  }

  {
    int64 rest = N, cost = 0;
    fill_n(dp2, 1000005, INF);
    fill_n(member, 100005, INF);
    for(int i = 1000004; i >= 0; i--) {
      if(rest == 0) dp2[i] = cost;

      for(auto &s : out[i]) {
        if(member[s.first] == INF) {
          --rest;
          member[s.first] = s.second;
          cost += s.second;
        } else if(s.second < member[s.first]) {
          cost -= member[s.first];
          member[s.first] = s.second;
          cost += member[s.first];
        }
      }
    }
  }

  int64 ret = INF;
  for(int i = 0; i < 1000005; i++) {
    if(i + K - 1 >= 1000005) continue;
    ret = min(ret, dp1[i] + dp2[i + K - 1]);
  }

  if(ret == INF) ret = -1;
  printf("%lld\n", ret);
}

C. Boredom

codeforces.com

問題概要

${n \times n(2 \le n \le 2 \times 10^5)}$ の行列があって ${i(1 \le i \le n)}$ 行目 ${p_i(1 \le p_i \le n)}$ 列目にはアがある. ${p_i}$ は相異なる.

行列からある四角形をとってきて, ${2}$ つの角にアがあるものを美しい四角形とする. 当然全部で ${\frac {n(n - 1)} {2}}$ 通りある.

ある矩形と共通部分を含む美しい四角形の個数を求める ${q(1 \le q \le 2 \times 10^5)}$ 個のクエリを全て処理せよ.

解法

なんか雰囲気的に, 美しい四角形より美しくない四角形のほうが数えやすい気がしてくるのでそっちを考える.

* がクエリで与えられた矩形の範囲とする.

____
_**_
____

まず矩形より上のマークのみを使ったペアは美しくない.

1111
_**_
____

同様に下のペアも美しくない.

____
_**_
2222

左のみ, 右のみも同様.

____
3**4
____

左上と左, 左と左下, 左上と左下のペア同士で構成しても美しくない.

5___
3**_
6___

右上と右, 右と右下, 右上と右下のペア同士も同様.

___7
_**4
___8

1番から8番までのそれぞれの矩形内のアの個数が求まればよくて, これは †Wavelet Matrix† を貼れば ${O(\log n)}$ . やったね.

ソース

貼っていきたい.

#include <bits/stdc++.h>

using namespace std;

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));
  }
};

typedef long long int64;

int main()
{
  int N, Q;

  scanf("%d %d", &N, &Q);
  vector< int > P(N);
  for(int i = 0; i < N; i++) {
    scanf("%d", &P[i]);
  }

  WaveletMatrix< int, 21 > mat(P);

  for(int i = 0; i < Q; i++) {
    int left, down, right, up;
    scanf("%d %d %d %d", &left, &down, &right, &up);
    int64 all = 1LL * N * (N - 1) / 2;

    int64 latte = down - 1;
    int64 malta = N - up;

    int64 beet1 = mat.rangefreq(0, left - 1, 0, down);
    int64 beet2 = mat.rangefreq(0, left - 1, down, up + 1);
    int64 beet3 = left - 1 - beet1 - beet2;
    int64 oioi1 = mat.rangefreq(right, N, 0, down);
    int64 oioi2 = mat.rangefreq(right, N, down, up + 1);
    int64 oioi3 = (N - right) - oioi1 - oioi2;

    all -= latte * (latte - 1) / 2;
    all -= malta * (malta - 1) / 2;

    all -= beet1 * beet2;
    all -= oioi1 * oioi2;

    all -= beet2 * beet3;
    all -= oioi2 * oioi3;

    all -= oioi1 * oioi3;
    all -= beet1 * beet3;

    all -= beet2 * (beet2 - 1) / 2;
    all -= oioi2 * (oioi2 - 1) / 2;

    printf("%lld\n", all);
  }
}

D. Michael and Charging Stations

codeforces.com

問題概要

${n(1 \le n \le 3 \times 10^5)}$ 日あって, ${i}$ 日目にはコスト ${a_i(a_i = 1000, 2000)}$ かかる.

またボーナスカードと呼ばれるものがあって, カードには支払額の ${\frac x 10}$ だけ貯金される. 貯金したぶんは次回以降の支払い時の一部に充てることができる. 最初の貯金額は ${0}$ である.

${n}$ 日間の最小コストを求めよ.

解法

よくわからないのでDPを考える.

まず貯金の単位は 100 の倍数に限定してもよさそう. また ${2000}$ より貯金しても意味はなさそう(使ったほうが良いので).

${dp[x][y] := }$ ${x}$ 日目まで見た時貯金が ${y}$ のときの最小コストとすると, 遷移は貯金をいくつ使うかになって, なんかはいになる(えー.

ソース

なんか通っちゃった.

#include <bits/stdc++.h>

using namespace std;

const int INF = 1 << 30;

int N, A[300000];
int dp[300001][21];

int main()
{
  scanf("%d", &N);
  for(int i = 0; i < N; i++) scanf("%d", &A[i]);

  fill_n(*dp, 21 * 300001, INF);
  dp[0][0] = 0;
  for(int i = 0; i < N; i++) {
    A[i] /= 100;
    for(int k = 20; k >= 0; k--) { // bounus rest
      if(dp[i][k] == INF) continue;
      for(int j = 0; j <= min(A[i], k); j++) { // bounus use
        int latte = min(20, (k - j) + (A[i] - j)/10);
        dp[i + 1][latte] = min(dp[i + 1][latte], dp[i][k] + (A[i] - j) * 100);
      }
    }
  }
  int ret = INF;
  for(int i = 20; i >= 0; i--) ret = min(ret, dp[N][i]);
  printf("%d\n", ret);
}

ei1333の日記

ぺこい

Codeforces Round #433 (Div. 1, based on Olympiad of Metropolises)

A. Planning

問題概要

解法

ソース

B. Jury Meeting

問題概要

解法

ソース

C. Boredom

問題概要

解法

ソース

D. Michael and Charging Stations

問題概要

解法

ソース