Codeforces Round #381 (Div. 1)

遅めの ${2}$ 完.
1999 -> 1988(-11).

A. Alyona and mex

問題概要

長さ ${n(1 \le n \le 10^5)}$ の非負整数列について, ${m}$ 個の部分列を取り出す. ${i}$ 番目は数列の区間 ${[l_i, r_i]}$ についてで, それぞれの部分列で mex を計算する. mex とは部分列内にない最小の非負整数である.

mex の最小値の最大値と, そのときの数列を出力せよ.

解法

${r_i - l_i + 1}$ の最小値がこの問題の解 ${x}$ となる.

${0, 1, 2, ..., x-1, 0, 1, 2, ..., x-1, ...}$ のような数列を作る. このとき, この数列のどの区間の長さ ${x}$ の部分列をとっても mex は ${x}$ である.

${r_i - l_i + 1}$ の最小値より大きい mex は明らかに実現できないため, これが解となる.

ソース

これに ${40}$ 分も悩んでたから面白い.

#include<bits/stdc++.h>

using namespace std;

const int INF = 1 << 30;

int main()
{
  int N, M;
  int K = INF;

  scanf("%d %d", &N, &M);
  for(int i = 0; i < M; i++) {
    int U, V;
    scanf("%d %d", &U, &V);
    K = min(K, V - U + 1);
  }
  cout << K << endl;
  for(int i = 0; i < N; i++) {
    cout << i % K << " ";
  }
}

B. Alyona and a tree

問題概要

${n}$ 頂点の根付き木がある. 根は頂点 ${1}$ である. それぞれの頂点には正整数 ${a_i}$ が書かれている. またそれぞれの辺にも正整数が書かれている.

${dist(u, v)}$ を頂点 ${v}$ と ${u}$ 間のパス上の辺に書かれた整数の和と定義する.

頂点 ${v}$ は, ${u}$ を制御する. ${u}$ は ${v}$ の子孫の頂点で ${dist(v, u) \le a_u}$ を満たす.

それぞれの頂点について, 何個の頂点を制御するか出力せよ.

解法

重心分解すると, 頂点 ${1}$ から頂点 ${v}$ 間のパスを列に落とせる. すると, 頂点 ${v}$ がどこの頂点まで制御されるか二分探索して求めることができる. 事前に累積させておけば ${O(n \log n)}$ .

データ構造をマージする一般的なテクでもできる. 頂点をのぼるとき頂点集合全体に辺のコストが加算されるので, その値を別に管理しておけばよい.

ソース

本番のときの重心分解したコード. オンラインだったらこっちかな.

#include<bits/stdc++.h>

using namespace std;
typedef long long int64;

vector< vector< int > > graph;

struct CentroidPathDecomposition
{
  struct Centroid
  {
    int ParIndex, ParDepth, Deep;
    vector< int > node;

    inline int size()
    {
      return (node.size());
    }

    inline int &operator[](int k)
    {
      return (node[k]);
    }

    inline pair< int, int > Up()
    {
      return (make_pair(ParIndex, ParDepth));
    }
  };

  vector< int > SubTreeSize, NextPath;
  vector< int > TreeIndex, TreeDepth;
  vector< Centroid > Centroids;

  void BuildSubTreeSize()
  {
    stack< pair< int, int > > s;
    s.push({0, -1});
    while(!s.empty()) {
      auto p = s.top();
      s.pop();
      if(~SubTreeSize[p.first]) {
        NextPath[p.first] = -1;
        for(auto &to : graph[p.first]) {
          if(p.second == to) continue;
          SubTreeSize[p.first] += SubTreeSize[to];
          if(NextPath[p.first] == -1 || SubTreeSize[NextPath[p.first]] < SubTreeSize[to]) {
            NextPath[p.first] = to;
          }
        }
      } else {
        s.push(p);
        SubTreeSize[p.first] = 1;
        for(auto &to : graph[p.first]) {
          if(p.second != to) s.push({to, p.first});
        }
      }
    }
  }

  void BuildPath()
  {
    stack< pair< int, int > > s;
    Centroids.push_back((Centroid) {-1, -1, 0});
    s.push({0, -1});
    TreeIndex[0] = 0;
    while(!s.empty()) {
      auto p = s.top();
      s.pop();
      TreeDepth[p.first] = Centroids[TreeIndex[p.first]].size();
      for(auto &to : graph[p.first]) {
        if(p.second != to) {
          if(to == NextPath[p.first]) { // Centroid-Path
            TreeIndex[to] = TreeIndex[p.first];
          } else {                  // Not Centroid-Path
            TreeIndex[to] = Centroids.size();
            Centroids.push_back((Centroid) {TreeIndex[p.first], TreeDepth[p.first], Centroids[TreeIndex[p.first]].Deep + 1});
          }
          s.push({to, p.first});
        }
      }
      Centroids[TreeIndex[p.first]].node.push_back(p.first);
    }
  }

  void AddEdge(int x, int y)
  {
    graph[x].push_back(y);
    graph[y].push_back(x);
  }

  void Build()
  {
    BuildSubTreeSize();
    BuildPath();
  }

  inline int size()
  {
    return (Centroids.size());
  }

  inline pair< int, int > Information(int idx)
  {
    return (make_pair(TreeIndex[idx], TreeDepth[idx]));
  }

  inline Centroid &operator[](int k)
  {
    return (Centroids[k]);
  }

  inline int LCA(int a, int b) // これを流用する
  {
    int TreeIdxA, TreeDepthA, TreeIdxB, TreeDepthB;
    tie(TreeIdxA, TreeDepthA) = Information(a);
    tie(TreeIdxB, TreeDepthB) = Information(b);
    while(TreeIdxA != TreeIdxB) {
      if(Centroids[TreeIdxA].Deep > Centroids[TreeIdxB].Deep) {
        tie(TreeIdxA, TreeDepthA) = Centroids[TreeIdxA].Up();
      } else {
        tie(TreeIdxB, TreeDepthB) = Centroids[TreeIdxB].Up();
      }
    }
    if(TreeDepthA > TreeDepthB) swap(TreeDepthA, TreeDepthB);
    return (Centroids[TreeIdxA][TreeDepthA]);
  }

  CentroidPathDecomposition(int SZ)
  {
    graph.resize(SZ);
    SubTreeSize.assign(SZ, -1);
    NextPath.resize(SZ);
    TreeIndex.resize(SZ);
    TreeDepth.resize(SZ);
  }

  void AddPath(int k);
};


struct CumulativeSum
{
  vector< int64 > data;

  CumulativeSum(int sz) : data(++sz, 0) {};

  inline void add(int k, int64 x)
  {
    data[k] += x;
  }

  void build()
  {
    for(int i = 1; i < data.size(); i++) {
      data[i] += data[i - 1];
    }
  }

  inline int64 query(int k)
  {
    if(k < 0) return (0);
    return (data[min(k, (int) data.size() - 1)]);
  }
};

int N, A[200000];
vector< CumulativeSum > bits, sums;
int U[200000], V[200000], L[200000];

void CentroidPathDecomposition::AddPath(int k)
{
  int length = A[k];
  int TreeIdxA, TreeDepthA;
  tie(TreeIdxA, TreeDepthA) = Information(k);
  while(TreeIdxA > 0) {
    int64 q = bits[TreeIdxA].query(TreeDepthA);
    if(length - q >= 0) {
      length -= q;
      sums[TreeIdxA].add(0, +1);
      sums[TreeIdxA].add(TreeDepthA + 1, -1);
      tie(TreeIdxA, TreeDepthA) = Centroids[TreeIdxA].Up();
    } else {
      break;
    }
  }
  int low = 0, high = TreeDepthA;
  int64 S = bits[TreeIdxA].query(TreeDepthA);
  while(high - low > 0) {
    int mid = (low + high) >> 1;
    if(S - bits[TreeIdxA].query(mid) <= length) {
      high = mid;
    } else {
      low = mid + 1;
    }
  }
  sums[TreeIdxA].add(low, +1);
  sums[TreeIdxA].add(TreeDepthA + 1, -1);
}

int main()
{
  scanf("%d", &N);
  for(int i = 0; i < N; i++) {
    scanf("%d", &A[i]);
  }
  CentroidPathDecomposition tree(N);
  for(int i = 1; i < N; i++) {
    int par, cost;
    scanf("%d %d", &par, &cost);
    --par;
    tree.AddEdge(par, i);
    U[i] = par, V[i] = i, L[i] = cost;
  }

  tree.Build();
  for(int i = 0; i < tree.size(); i++) {
    sums.push_back(CumulativeSum(tree[i].size() + 1));
    bits.push_back(CumulativeSum(tree[i].size() + 1));
  }
  for(int i = 1; i < N; i++) {
    if(tree.SubTreeSize[U[i]] < tree.SubTreeSize[V[i]]) swap(U[i], V[i]);
    int p, q;
    tie(p, q) = tree.Information(V[i]);
    bits[p].add(q, L[i]);
  }
  for(int i = 0; i < bits.size(); i++) {
    bits[i].build();
  }
  for(int i = 0; i < N; i++) {
    tree.AddPath(i);
  }
  for(int i = 0; i < sums.size(); i++) {
    sums[i].build();
  }
  for(int i = 0; i < N; i++) {
    int p, q;
    tie(p, q) = tree.Information(i);
    printf("%lld ", sums[p].query(q) - 1);
  }
  puts("");
}

データ構造をマージする一般的なテクの解. シンプル.

#include<bits/stdc++.h>

using namespace std;

typedef long long int64;

struct edge
{
  int to, cost;
};

int N, A[200000];
vector< edge > g[200000];

multiset< int64 > q[200000];
int64 add[200000];
int ret[200000];

void rec(int idx, int par = -1)
{
  for(auto &e : g[idx]) {
    if(par == e.to) continue;
    rec(e.to, idx);
    add[e.to] += e.cost;
    while(!q[e.to].empty() && *q[e.to].begin() < add[e.to]) {
      q[e.to].erase(q[e.to].begin());
    }
    if(q[idx].size() < q[e.to].size()) {
      swap(q[idx], q[e.to]);
      swap(add[idx], add[e.to]);
    }
    while(!q[e.to].empty()) {
      q[idx].insert(*q[e.to].begin() - add[e.to] + add[idx]);
      q[e.to].erase(q[e.to].begin());
    }
  }
  ret[idx] = (int) q[idx].size();
  q[idx].insert(A[idx] + add[idx]);
}

int main()
{
  scanf("%d", &N);
  for(int i = 0; i < N; i++) {
    scanf("%d", &A[i]);
  }
  for(int u = 1; u < N; u++) {
    int v, x;
    scanf("%d %d", &v, &x);
    g[--v].push_back((edge) {u, x});
  }
  rec(0);
  for(int i = 0; i < N; i++) printf("%d ", ret[i]);
  puts("");
}

ei1333の日記

ぺこい

Codeforces Round #381 (Div. 1)

A. Alyona and mex

問題概要

解法

ソース

B. Alyona and a tree

問題概要

解法

ソース