Codeforces Round #431 (Div. 1)

3完したかったなあ.

ABの 2 完で 2096 -> 2181(+85). 上の色が突然見えてきた. なんかこんな上がるものだっけ.

直近2回の上がり方, 過去をこわしている pic.twitter.com/xy1GpbmNg8
— うし (@ei1333) 2017年9月1日

A. From Y to Y

問題概要

${n}$ 個の文字からなる多重集合に対して ${n - 1}$ 回の以下の操作を行って, ${n}$ 文字からなる文字列を構成する.

集合から ${2}$ つの要素 ${s, t}$ を削除し, ${s + t}$ を追加する.

${1}$ 回の操作につきコスト ${\sum_{c \in \{a, b, \dots, z \}} f(s, c) \times f(t, c)}$ がかかる. ここで, ${f(s, c)}$ は文字列 ${s}$ 中の文字 ${c}$ の出現回数である.

操作全体にかかる最小コストがちょうど ${k(0 \le k \le 10^5)}$ となるような文字列を構成せよ.

解法

A問題なので, 最小コストはどうせそれぞれの文字の出現回数とかで決まりそう. 終わり.

コストは文字種ごとに独立なので ${1}$ 種類からなる文字列の構成コストを考える.

a: 0
aa: 1
aaa: 3
aaaa: 6
aaaaa: 10
aaaaaa: 15

はい(はいなので). ある ${1}$ 文字が最終的なコストに寄与する分を考えると, どのように操作しても ${\frac {n(n - 1)} {2}}$ とコストは一致する.

あとは適当.

ソース

#include<bits/stdc++.h>

using namespace std;

int main()
{
  int K;
  cin >> K;
  string S;

  for(char c = 'a'; c <= 'z'; c++) {
    int sum = 0;
    while(K - sum >= 0) {
      K -= sum;
      S += c;
      ++sum;
    }
  }

  cout << S << endl;
}

B. Rooter’s Song

codeforces.com

問題概要

${w \times h(2 \le w, h \le 10^5)}$ の矩形のステージがある. ステージの側面には ${n(1 \le n \le 10^5)}$ 人のダンサーがいて, それぞれ次のいずれかに分類される.

Vertical: ${(x_i, 0)}$ から正の y 方向(上向き)に向かって移動する.
Horizontal: ${(0, y_i)}$ から正の x 方向(右向き)に向かって移動する.

${i}$ 番目のダンサーは ${t_i}$ ms経過後に移動を開始し, 境界に達するまで 1 ms ごとに単位距離進み続ける.

${2}$ 人のダンサーが衝突したとき, 移動方向を交換する.

すべてのダンサーの停止位置を求めよ.

解法

すごく蟻っぽい.

まずぐっと睨むと ${y_i - t_i}$ と ${x_i - t_i}$ が等しいもの同士については衝突するタイミングが一致(別のダンサーと交差すれば必ずそこで移動方向が交換される)し, それ以外は衝突しないことがわかるので, この値で場合分けして独立して解く.

以下のような感じのアがあるとする.

   |   |
4 -------
   |   |
3 -------
   |   |
   1   2

最終的なダンサーはシミュレーションすると, 以下のようになるのはそれはそう.

   4   3
   |   |
4 ------- 1
   |   |
3 ------- 2
   |   |
   1   2

上方向に移動するダンサーたちを x 軸の値でソートして, x が小さいほうから追加していく.

   4
   |     ↑
4 ------- 3
   |     ↑
3 ------- 1
   |     ↑
   1

一番最初のアを追加した場面. この操作は右方向のダンサーについて, 下からダンサー(1)を追加して一番上のダンサー(4)を上に押し出す操作に相当しそうな気がしてくる.

   4   3
   |   | ↑
4 ------- 1
   |   | ↑
3 ------- 2
   |   | ↑
   1   2

でこれは queue にエンキューしてデキューする操作に相当するので, それをえいってやればよい. びーと.

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

ソース

問題見て一目散にPCKの蟻の解説に飛びついていったけど解説がよくわからず悲しい気持ちになった. またAOJも落ちていたため.

グループ分けして処理するのは分かっていたので自分で考えたほうがはやかったかなぁ.

#include<bits/stdc++.h>

using namespace std;

int main()
{
  int N, W, H, G[100000], P[100000], T[100000];

  scanf("%d %d %d", &N, &W, &H);
  for(int i = 0; i < N; i++) {
    scanf("%d %d %d", &G[i], &P[i], &T[i]);
  }

  map< int, vector< int > > xy;
  for(int i = 0; i < N; i++) {
    xy[P[i] - T[i]].push_back(i);
  }

  vector< int > num(N);
  iota(begin(num), end(num), 0);

  for(auto &vs : xy) {
    vector< pair< int, int > > toup, toleft;
    for(int j : vs.second) {
      if(G[j] == 1) toup.emplace_back(P[j], j);
      else toleft.emplace_back(P[j], j);
    }
    sort(begin(toup), end(toup));
    sort(begin(toleft), end(toleft));
    reverse(begin(toleft), end(toleft));

    queue< int > que;
    for(auto &p : toleft) que.emplace(p.second);

    for(int i = 0; i < toup.size(); i++) {
      if(!que.empty()) {
        int p = que.front();
        que.pop();
        num[toup[i].second] = p;
        que.push(toup[i].second);
      }
    }

    int tail = 0;
    while(!que.empty()) {
      int p = que.front();
      num[toleft[tail++].second] = p;
      que.pop();
    }
  }

  int X[100000], Y[100000];
  for(int i = 0; i < N; i++) {
    const int idx = num[i];
    Y[idx] = G[i] == 1 ? H : P[i];
    X[idx] = G[i] == 2 ? W : P[i];
  }
  for(int i = 0; i < N; i++) {
    printf("%d %d\n", X[i], Y[i]);
  }
}

C. Goodbye Souvenir

codeforces.com

問題概要

長さ ${n(1 \le n \le 10^5)}$ の数列 ${a_i(1 \le a_i \le n)}$ が与えられる.

${m(1 \le m \le 10^5)}$ 個のクエリを順に処理せよ.

要素 ${p}$ を ${x}$ に更新する.
区間 ${[l, r]}$ のアレを求める. ここでアレは, 区間に ${1}$ 回以上出現するすべての値 ${x}$ について, (区間内の最後の出現位置 - 区間内の最初の出現位置) をすべて足し合わせたものである.

解法

矩形sumクエリに帰着する.

区間内で ${x}$ が出現した位置が ${b_1, b_2, \dots, b_k}$ だったとする. (区間内の最後の出現位置 - 区間内の最初の出現位置) というのは ${(b_2 - b_1) + (b_3 - b_2) + \dots + (b_k - b_{k-1})}$ と等価.

それぞれの要素 ${a_i}$ について, ${i}$ 以前に出現した値 ${a_i}$ の最も右の出現位置を ${b_i}$ とする. ${b_i}$ は, 種類ごとに set とかでえいしておけば ${O(\log n)}$ で求めることができる. また ${c_i = i - b_i}$ としておく.

それぞれのクエリで求めたいものは ${\sum_{l \le i \le r, l \le b_i} c_i}$ である. ${b_i}$ を高さとみなして言い換えると, 区間 ${[l, r]}$ 内のうち, 高さ ${l}$ 以上にある要素 ${c_i}$ の総和である.

これは二次元の矩形和になっていて, セグ木にBITを乗せればできる(えーん. 普通にやると範囲がアなので, クエリで出現する列を先読みし, それをあらかじめ座圧してからやると ${O(q \log^2 n)}$ になる.

更新クエリが結構面倒だけど, なんかいい感じにイメージしてやる.

ソース

†セグ木†

シンプルに考えれば解けてたかなぁ…たぶん解けてないね.

#include<bits/stdc++.h>

using namespace std;

typedef long long int64;

template< class T >
struct BinaryIndexedTree
{
  vector< T > data;

  BinaryIndexedTree(int sz)
  {
    data.assign(++sz, 0);
  }

  T sum(int k)
  {
    T ret = 0;
    for(++k; k < data.size(); k += k & -k) ret += data[k];
    return (ret);
  }

  void add(int k, T x)
  {
    k = min(k, (int)data.size() - 2);
    for(++k; k > 0; k -= k & -k) data[k] += x;
  }
};

struct SegmentTree
{
  int sz;
  vector< vector< int > > nums;
  vector< BinaryIndexedTree< int64 > > seg;

  SegmentTree(vector< vector< int > > sg)
  {
    sz = 1;
    while(sz < sg.size()) sz <<= 1;
    nums.resize(2 * sz - 1);
    for(int i = 0; i < sg.size(); i++) nums[sz + i - 1] = sg[i];
    for(int i = sz - 2; i >= 0; i--) {
      nums[i].resize(nums[2 * i + 1].size() + nums[2 * i + 2].size());
      merge(begin(nums[2 * i + 1]), end(nums[2 * i + 1]), begin(nums[2 * i + 2]), end(nums[2 * i + 2]), begin(nums[i]));
    }
    for(int i = 0; i < 2 * sz - 1; i++) seg.push_back(BinaryIndexedTree< int64 >(nums[i].size()));
  }

  void update(int x, int y, int64 z)
  {
    x += sz - 1;
    seg[x].add(lower_bound(begin(nums[x]), end(nums[x]), y) - begin(nums[x]), z);
    while(x > 0) {
      x = (x - 1) >> 1;
      seg[x].add(lower_bound(begin(nums[x]), end(nums[x]), y) - begin(nums[x]), z);
    }
  }

  int64 query(int a, int b, int k, int l, int r)
  {
    if(a >= r || b <= l) return (0);
    if(a <= l && r <= b) return (seg[k].sum(lower_bound(begin(nums[k]), end(nums[k]), a) - begin(nums[k])));
    return (query(a, b, 2 * k + 1, l, (l + r) >> 1) + query(a, b, 2 * k + 2, (l + r) >> 1, r));
  }

  int64 query(int a, int b)
  {
    return (query(a, b, 0, 0, sz));
  }
};

int main()
{
  int N, M, A[100000];
  set< int > st[100001];
  int T[100000], X[100000], Y[100000];


  scanf("%d %d", &N, &M);
  for(int i = 0; i < N; i++) {
    scanf("%d", &A[i]);
    st[A[i]].emplace(i);
  }
  for(int i = 1; i <= N; i++) st[i].emplace(N);


  vector< tuple< int, int, int > > qs[100001];
  vector< vector< int > > sg(N + 1);
  auto push = [&](int idx, int a, int b, int c)
  {
    sg[a].push_back(b);
    qs[idx].emplace_back(a, b, c);
  };

  for(int i = 0; i < N; i++) {
    auto it = st[A[i]].lower_bound(i);
    if(it != begin(st[A[i]])) push(100000, *it, *prev(it), *it - *prev(it));
  }

  for(int i = 0; i < M; i++) {
    scanf("%d %d %d", &T[i], &X[i], &Y[i]);
    --X[i];
    if(T[i] == 1) {
      auto it = st[A[X[i]]].lower_bound(X[i]);
      if(it != begin(st[A[X[i]]])) push(i, *it, *prev(it), *prev(it) - *it);
      push(i, *next(it), *it, *it - *next(it));
      it = st[A[X[i]]].erase(it);
      if(it != begin(st[A[X[i]]])) push(i, *it, *prev(it), *it - *prev(it));

      A[X[i]] = Y[i];
      it = st[A[X[i]]].lower_bound(X[i]);
      if(it != begin(st[A[X[i]]])) push(i, *it, *prev(it), *prev(it) - *it);
      st[A[X[i]]].emplace(X[i]);
      it = st[A[X[i]]].lower_bound(X[i]);
      if(it != begin(st[A[X[i]]])) push(i, *it, *prev(it), *it - *prev(it));
      ++it;
      push(i, *it, *prev(it), *it - *prev(it));
    }
  }

  for(int i = 0; i < N; i++) {
    sort(begin(sg[i]), end(sg[i]));
    sg[i].erase(unique(begin(sg[i]), end(sg[i])), end(sg[i]));
  }

  SegmentTree seg(sg);
  auto dodo = [&](int idx)
  {
    for(auto& p : qs[idx]) {
      int a, b, c;
      tie(a, b, c) = p;
      seg.update(a, b, c);
    }
  };
  dodo(100000);

  for(int i = 0; i < M; i++) {
    if(T[i] == 1) dodo(i);
    else printf("%lld\n", seg.query(X[i], Y[i]));
  }
}

ei1333の日記

ぺこい

Codeforces Round #431 (Div. 1)

A. From Y to Y

問題概要

解法

ソース

B. Rooter’s Song

問題概要

解法

ソース

C. Goodbye Souvenir

問題概要

解法

ソース