World CodeSprint 12 - ei1333の日記

www.hackerrank.com

69thなのでパーカーを得た

The Salesman

問題概要

わすれた

解法

わすれた

ソースコード

#include <bits/stdc++.h>

using namespace std;

using int64 = long long;

int main()
{
  int T, N, X[50];

  cin >> T;
  while(T--) {
    cin >> N;
    for(int i = 0; i < N; i++) {
      cin >> X[i];
    }
    sort(X, X + N);
    cout << X[N - 1] - X[0] << endl;
  }
}

Red Knight's Shortest Path

問題概要

${n \times n(5 \le n \le 200)}$ のグリッドがある.

${(i_{start}, j_{start})}$ にある red knight を, 6種類の動き方(原文図参照, 優先順位は UL, UR, R, LR, LL, L)を用いて ${(i_{end}, j_{end})}$ に移動させる.

移動が可能なら最短操作回数かつ優先順位に基いて動かした時の操作手順を出力せよ.

解法

すなおに虚無BFSして経路復元をします. ゴールからみるとやりやすいかも.

ソース

#include <bits/stdc++.h>

using namespace std;

using int64 = long long;

const int vy[] = {-2, -2, 0, 2, 2, 0};
const int vx[] = {-1, 1, 2, 1, -1, -2};
const string vs[] = {"UL", "UR", "R", "LR", "LL", "L"};

int main()
{
  int N, A, B, C, D;

  cin >> N;
  cin >> A >> B >> C >> D;

  int mat[200][200];
  memset(mat, -1, sizeof(mat));
  queue< pair< int, int > > que;
  que.emplace(C, D);
  mat[C][D] = 0;

  while(!que.empty()) {
    int y, x;
    tie(y, x) = que.front();
    que.pop();
    for(int i = 0; i < 6; i++) {
      int ny = y + vy[i], nx = x + vx[i];
      if(ny < 0 || nx < 0 || ny >= N || nx >= N) continue;
      if(mat[ny][nx] != -1) continue;
      mat[ny][nx] = mat[y][x] + 1;
      que.emplace(ny, nx);
    }
  }

  if(mat[A][B] == -1) {
    cout << "Impossible" << endl;
    return (0);
  }

  cout << mat[A][B] << endl;

  bool first = false;
  while(A != C || B != D) {
    for(int i = 0; i < 6; i++) {
      int ny = A + vy[i], nx = B + vx[i];
      if(ny < 0 || nx < 0 || ny >= N || nx >= N) continue;
      if(mat[ny][nx] + 1 == mat[A][B]) {
        A = ny;
        B = nx;
        if(first++) cout << " ";
        cout << vs[i];
        break;
      }
    }
  }

  cout << endl;
}

Breaking Sticks

問題概要

${n(1 \le n \le 100)}$ 個のチョコがあって, ${i}$ 番目のチョコは ${a_i(1 \le a_i \le 10^12)}$ 個のピースが繋がっている. このチョコに対し次のいずれかの操作を繰り返し行う.

現在あるチョコの部品から 1 つ選んでたべる.
現在あるチョコの部品から 1 つ選んで, 整数長の等しい長さを持つ複数の部品に分割する.

操作回数の最大値を求めよ

解法

どうみても ${O(n \sqrt a_i)}$ なので, ${a_i}$ を素因数分解してみる.

整数長への分割なので, そのピースの大きさの素因数に含まれるいずれかの値で割る以外の方法はない.

えーとりあえずソースコードを書くと, 式的に最大の素因数で割っていくのが最適だということを示せそうなため.

ソース

#include <bits/stdc++.h>

using namespace std;

using int64 = long long;

map< int64, int > prime_factor(int64 n)
{
  map< int64, int > ret;
  for(int64 i = 2; i * i <= n; i++) {
    while(n % i == 0) {
      ret[i]++;
      n /= i;
    }
  }
  if(n != 1) ret[n] = 1;
  return (ret);
}

int main()
{
  int N;
  cin >> N;
  int64 all = 0;
  while(N--) {
    int64 X;
    cin >> X;
    auto p = prime_factor(X);
    int64 cur = X;
    vector< pair< int64, int64 > > vs(p.begin(), p.end());
    sort(vs.rbegin(), vs.rend());
    for(auto s : vs) {
      while(s.second > 0) {
        all += X / cur;
        cur /= s.first;
        --s.second;
      }
    }
    all += X;
  }
  cout << all << endl;
}

Factorial Array

問題概要

長さ ${n(1 \le n \le 10^5)}$ の数列 ${A_i(1 \le A_i \le 10^9)}$ がある.

以下の ${m(1 \le m \le 10^5)}$ 個のクエリを全て処理せよ.

区間 ${[l, r]}$ に一様に ${1}$ を加算
区間 ${[l, r]}$ のそれぞれの要素について ${A_i!}$ を求めその総和を ${10^9}$ で割った余りで求める
要素 ${A_i}$ を値 ${v}$ にする

解法

なんかここらへんの問題から†データ構造† 実家のような安心感が続く気がする.

ずっとmodが ${10^9+7}$ だと思っていたため不可能だと思っていた.

mod が ${10^9}$ なので, ${A_i \ge 40}$ の要素はすべて ${40}$ とみなしてもよい. ${40!}$ を ${10^9}$ で割った余りは ${0}$ なのでそれ以降はすべて ${0}$ .

これはなんかセグメント木に長さ ${40}$ のベクトルをのせる気持ちになるととけるため. 区間加算は遅延評価する.

ソース

#include <bits/stdc++.h>

using namespace std;

const int mod = 1e9;


struct SegmentTree
{
  vector< vector< int > > seg;
  vector< int > add;
  int sz;
  int fact[41];

  SegmentTree(int n)
  {
    sz = 1;
    while(sz < n) sz <<= 1;
    fact[0] = 1;
    for(int i = 1; i < 41; i++) {
      fact[i] = 1LL * fact[i - 1] * i % mod;
    }
    seg.assign(2 * sz - 1, vector< int >(41, 0));
    add.assign(2 * sz - 1, 0);
  }

  inline void push(int k)
  {
    if(k < sz - 1) {
      add[2 * k + 1] += add[k];
      add[2 * k + 2] += add[k];
    }
    vector< int > renew(41, 0);
    for(int i = 0; i < 41; i++) {
      renew[min(40, i + add[k])] += seg[k][i];
    }
    renew.swap(seg[k]);
    add[k] = 0;
  }

  int query(int a, int b, int k, int l, int r)
  {
    push(k);
    if(a >= r || b <= l) return (0);
    if(a <= l && r <= b) {
      int ret = 0;
      for(int i = 0; i < 41; i++) {
        ret += 1LL * seg[k][i] * fact[i] % mod;
        ret %= mod;
      }
      return (ret);
    }
    return (query(a, b, 2 * k + 1, l, (l + r) >> 1) + query(a, b, 2 * k + 2, (l + r) >> 1, r)) % mod;
  }

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

  inline void merge(int k)
  {
    for(int i = 0; i < 41; i++) {
      seg[k][i] = seg[2 * k + 1][i] + seg[2 * k + 2][i];
    }
  }

  void addd(int a, int b, int k, int l, int r)
  {
    push(k);
    if(a >= r || b <= l) return;
    if(a <= l && r <= b) {
      ++add[k];
      push(k);
      return;
    }
    addd(a, b, 2 * k + 1, l, (l + r) >> 1);
    addd(a, b, 2 * k + 2, (l + r) >> 1, r);
    merge(k);
  }


  void update(int a, int x, int k, int l, int r)
  {
    push(k);
    if(a >= r || a + 1 <= l) return;
    if(a <= l && r <= a + 1) {
      for(int i = 0; i < 41; i++) seg[k][i] = 0;
      seg[k][x] = 1;
      return;
    }
    update(a, x, 2 * k + 1, l, (l + r) >> 1);
    update(a, x, 2 * k + 2, (l + r) >> 1, r);
    merge(k);
  }

  void addd(int a, int b)
  {
    addd(a, b, 0, 0, sz);
  }

  void update(int a, int x)
  {
    update(a, x, 0, 0, sz);
  }
};

int main()
{
  int N, M, A[100000];
  scanf("%d %d", &N, &M);
  for(int i = 0; i < N; i++) {
    scanf("%d", &A[i]);
  }
  SegmentTree seg(N);
  for(int i = 0; i < N; i++) {
    seg.update(i, min(A[i], 40));
  }
  for(int i = 0; i < M; i++) {
    int a, b, c;
    scanf("%d %d %d", &a, &b, &c);
    --b;
    if(a == 1) {
      seg.addd(b, c);
    } else if(a == 2) {
      printf("%d\n", seg.query(b, c));
    } else {
      seg.update(b, min(c, 40));
    }
  }
}

Animal Transport

問題概要

${m(1 \le m \le 5 \times 10^4)}$ 個の動物園に並んでいて, ${1}$ から ${m}$ までの番号付けがされている.

${n(1 \le n \le 5 \times 10^4)}$ 匹の動物がいて, それぞれは動物園 ${s_i}$ から ${d_i}$ に移動しようとして, また動物 'E', 'D', 'C', 'M' のいずれかである.

無限容量を載せられるバスを用いて動物を移動させる. ただし 'E' と 'D', 'D' と 'C', 'C' と 'M', 'M' と 'E' のペアの動物を同時にのせるとヤバいため, この操作はできない. また動物園は昇順に訪れる必要がある.

${n}$ 個の動物のうち ${1}$ 匹から ${n}$ 匹の動物を適切に選んで移動させるそれぞれの場合について, 移動をすべて終えることのできる最小の動物園の番号を求めよ.

解法

同時にのせるとヤバい条件をぐっと睨むと, バスの各地点の状態を見た時に載っている動物は {'E','C'} のみ(タイプ 1 とする)か {'D', 'M'} のみ(タイプ 2 とする)かのいずれか.

また dp することを考えると, dp[idx] := 動物園 idx までで移動を終えることができる動物の最大匹数をそれぞれのidxについて求めればあとは適当にえいすれば答えがわかる. よって dp[idx] をどう求めるかが問題となる.

するとタイプ 1 とタイプ 2 の重複しない区間をいい感じに選ぶ問題に帰着できる.

動物園 ${id}$ にいるある動物 ${idx}$ を運ぶと仮定すると, 少なくともその動物が目的地 ${d_{idx}}$ に到達するまでのタイプは ${1}$ か ${2}$ で固定である. そこで dp2[type][p] := 動物園 ${p}$ までの区間のタイプが ${type}$ のときの動物の最大匹数のような補助的なDP配列を定義すると上手くいくことがわかる. 動物 ${idx}$ を運ぶと仮定する. 新しいタイプの区間を生やす場合は dp2[type][d_{idx}] = dp[idx] + 1. 直前の同様のタイプをのばす場合は dp2[type] の区間 ${[1, d_i)}$ の max + 1 みたいな感じになり, 直前の同様のタイプに内包させる場合を考えると dp2[type] の ${d_i}$ 以降の区間 ${1}$ 加算になるためこれもさっきの問題とおなじで遅延評価のセグメント木でえいする.

ソース

#include <bits/stdc++.h>

using namespace std;

const int INF = 1 << 30;

struct SegmentTree
{
  int sz;
  vector< int > seg, add;

  SegmentTree(int n)
  {
    sz = 1;
    while(sz < n) sz <<= 1;
    seg.assign(2 * sz - 1, -INF);
    add.assign(2 * sz - 1, 0);
  }

  inline void push(int k)
  {
    if(k < sz - 1) {
      add[2 * k + 1] += add[k];
      add[2 * k + 2] += add[k];
    }
    seg[k] += add[k];
    add[k] = 0;
  }

  int query(int a, int b, int k, int l, int r)
  {
    push(k);
    if(a >= r || b <= l) return (-INF);
    if(a <= l && r <= b) return (seg[k]);
    return max(query(a, b, 2 * k + 1, l, (l + r) >> 1), query(a, b, 2 * k + 2, (l + r) >> 1, r));
  }

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

  void addd(int a, int b, int k, int l, int r)
  {
    push(k);
    if(a >= r || b <= l) return;
    if(a <= l && r <= b) {
      ++add[k];
      push(k);
      return;
    }
    addd(a, b, 2 * k + 1, l, (l + r) >> 1);
    addd(a, b, 2 * k + 2, (l + r) >> 1, r);
    seg[k] = max(seg[2 * k + 1], seg[2 * k + 2]);
  }

  void update(int a, int x, int k, int l, int r)
  {
    push(k);
    if(a >= r || a + 1 <= l) return;
    if(a <= l && r <= a + 1) {
      seg[k] = max(seg[k], x);
      return;
    }
    update(a, x, 2 * k + 1, l, (l + r) >> 1);
    update(a, x, 2 * k + 2, (l + r) >> 1, r);
    seg[k] = max(seg[2 * k + 1], seg[2 * k + 2]);
  }

  void addd(int a, int b)
  {
    addd(a, b, 0, 0, sz);
  }

  void update(int a, int x)
  {
    update(a, x, 0, 0, sz);
  }
};

const string temp = "EDCM";

void myon()
{
  int M, N;
  int T[50000], S[50000], D[50000];
  int dp[50000], ans[50001];


  scanf("%d %d", &M, &N);
  for(int i = 0; i < N; i++) {
    char c;
    scanf(" %c", &c);
    T[i] = (int) temp.find(c);
  }
  for(int i = 0; i < N; i++) {
    scanf("%d", &S[i]);
    --S[i];
  }
  for(int i = 0; i < N; i++) {
    scanf("%d", &D[i]);
    --D[i];
  }

  vector< int > ev[50000];
  for(int i = 0; i < N; i++) {
    ev[S[i]].emplace_back(i);
  }

  vector< SegmentTree > seg(2, SegmentTree(M));
  fill_n(ans, N + 1, INF);
  for(int i = 0; i < 2; i++) {
    seg[i].update(0, 0);
  }

  for(int i = 0; i < M; i++) {
    if(i > 0) {
      dp[i] = -INF;
      for(int j = 0; j < 2; j++) {
        dp[i] = max(dp[i], seg[j].query(0, i + 1));
      }
    }
    for(int idx : ev[i]) {
      if(S[idx] < D[idx]) {
        seg[T[idx] % 2].addd(D[idx], M);
        seg[T[idx] % 2].update(D[idx], max(dp[i], seg[T[idx] % 2].query(0, D[idx])) + 1);
      }
    }
    ans[dp[i]] = min(ans[dp[i]], i + 1);
  }
  for(int i = N - 1; i >= 0; i--) {
    ans[i] = min(ans[i], ans[i + 1]);
  }
  for(int i = 1; i <= N; i++) {
    if(ans[i] >= INF) ans[i] = -1;
    if(i > 1) putchar(' ');
    printf("%d", ans[i]);
  }
  puts("");
}

int main()
{
  int T;
  scanf("%d", &T);
  while(T--) myon();
}

Keko the Brilliant

問題概要

${n(1 \le n \le 2 \times 10^5)}$ の根付き木が与えられる. それぞれの頂点には値 ${r_i(1 \le r_i \le 10^9)}$ が割り当てられている.

好きな頂点の値を好きな値に変更する操作を繰り返して, すべての頂点 ${i}$ を見た時に, その部分木の頂点がもつ値が ${r_i}$ 以上になるようにしたい.

最小操作回数を求めよ.

解法

自然な考察をすると最悪が生えるため, それを実装すると通る.

問題の見た目からDP配列をデータ構造をマージするテクで ${O(n \log n)}$ で解くやつのようにみえる.

なんか最長増加部分列を求めるような気分を思い出すと dp[idx][x] := 頂点 idx を値 x にするとき, その部分木で変更しない値の頂点数の最大値みたいなアが生える. 問題の解は ${n}$ - min(dp[0][i]) と一致する.

考えられる値の個数はそれぞれの頂点についてその部分木の頂点数に抑えられるため, 値ひとつのマージが ${O(\log n)}$ でできるのでマージテクを用いて ${O(n \log^2 n)}$ で解けることがわかる.

えーその頂点について何個かの子のマージは終わっているとする(dp1). ある子のDP配列(dp2とする)をこれにマージすることを考える.

dp2のうちの値 x をその頂点の dp 配列に追加することを考えると, なんか dp1 の x は dp2の x 以上のRMQの値と dp1 の x 以下のRMQみたいなアレになって, dp1 の x 未満のアに dp2 の x 以上の RMQ を一様加算みたいなえぇ....になる.

これは遅延平衡二分木でできるためそれを書くとできる(最悪

ここではRBSTを遅延に書き換えた(無限にバグったため.

ソース

#include <bits/stdc++.h>

using namespace std;

int xor128(void)
{
  static int x = 123456789;
  static int y = 362436069;
  static int z = 521288629;
  static int w = 88675123;
  int t;

  t = x ^ (x << 11);
  x = y;
  y = z;
  z = w;
  return w = (w ^ (w >> 19)) ^ (t ^ (t >> 8));
}

struct Node
{
  int key, value;
  int SubTreeSize;
  Node *Lch, *Rch;
  int add;
  int rmq;

  Node(int key, int value) : key(key), value(value), SubTreeSize(1), add(0), rmq(value)
  {
    Lch = (Node *) NULL;
    Rch = (Node *) NULL;
  };
};

inline int Count(Node *t)
{
  if(t == (Node *) NULL) return (0);
  else return (t->SubTreeSize);
}

inline Node *Update(Node *t)
{
  t->SubTreeSize = Count(t->Lch) + Count(t->Rch) + 1;
  t->rmq = t->value;
  if(t->Lch) t->rmq = max(t->rmq, t->Lch->rmq + t->Lch->add);
  if(t->Rch) t->rmq = max(t->rmq, t->Rch->rmq + t->Rch->add);
  return (t);
}

inline Node *MakeRoot(int key, int value)
{
  return (new Node(key, value));
}

void push(Node *p)
{
  if(p == (Node *) NULL) return;
  if(p->Lch != (Node *) NULL) p->Lch->add += p->add;
  if(p->Rch != (Node *) NULL) p->Rch->add += p->add;
  p->value += p->add;
  p->rmq += p->add;
  p->add = 0;
}

Node *Merge(Node *l, Node *r)
{
  push(l);
  push(r);
  if(l == (Node *) NULL) return (r);
  if(r == (Node *) NULL) return (l);
  int Left = l->SubTreeSize;
  int Right = r->SubTreeSize;
  if(xor128() % (Left + Right) < Left) {
    l->Rch = Merge(l->Rch, r);
    return (Update(l));
  } else {
    r->Lch = Merge(l, r->Lch);
    return (Update(r));
  }
}

pair< Node *, Node * > Split(Node *t, int k) // [0, k), [k, n)
{
  push(t);
  if(t == (Node *) NULL) return (make_pair((Node *) NULL, (Node *) NULL));
  if(k <= Count(t->Lch)) {
    pair< Node *, Node * > s = Split(t->Lch, k);
    t->Lch = s.second;
    return (make_pair(s.first, Update(t)));
  } else {
    pair< Node *, Node * > s = Split(t->Rch, k - Count(t->Lch) - 1);
    t->Rch = s.first;
    return (make_pair(Update(t), s.second));
  }
}

int Lower_Bound(Node *root, int key)
{
  push(root);
  if(root == (Node *) NULL) return (0);
  if(key <= root->key) return (Lower_Bound(root->Lch, key));
  return (Lower_Bound(root->Rch, key) + Count(root->Lch) + 1);
}

int N, R[200000];
vector< int > g[200000];
Node *root[200000];

inline void rec(int idx, int par)
{
  for(auto &to : g[idx]) {
    if(to == par) continue;
    rec(to, idx);

    if(Count(root[idx]) < Count(root[to])) {
      swap(root[idx], root[to]);
    }

    int pvkey = -100;

    while(Count(root[to]) > 0) {
      assert(root[to]->add == 0);
      int curr_node_cost = root[to]->rmq;

      auto buff = Split(root[to], 1);
      root[to] = buff.second;

      auto p = buff.first;
      auto q = Split(root[idx], Lower_Bound(root[idx], pvkey + 1)); // ..pvkey](pvkey+1,
      auto r = Split(q.second, Lower_Bound(q.second, p->key)); // curkey)[curkey,...
      if(r.first) r.first->add += curr_node_cost;
      if(r.second) curr_node_cost += r.second->rmq;

      auto s = Split(r.second, 1);
      if(s.first) {
        if(s.first->key == p->key) r.second = s.second;
        else r.second = Merge(s.first, s.second);
      }

      root[idx] = Merge(q.first, Merge(r.first, Merge(MakeRoot(p->key, curr_node_cost), r.second)));

      pvkey = p->key;
    }
  }

  auto p = Split(root[idx], Lower_Bound(root[idx], R[idx]));
  int curr_node_cost = 1;
  if(p.second) curr_node_cost += p.second->rmq;
  auto q = Split(p.second, 1);
  if(q.first) {
    if(q.first->key == R[idx]) p.second = q.second;
    else p.second = Merge(q.first, q.second);
  }
  root[idx] = Merge(p.first, Merge(MakeRoot(R[idx], curr_node_cost), p.second));
}

int main()
{
  scanf("%d", &N);
  for(int i = 0; i < N; i++) {
    scanf("%d", &R[i]);
  }
  for(int i = 1; i < N; i++) {
    int x, y;
    scanf("%d %d", &x, &y);
    --x, --y;
    g[x].emplace_back(y);
    g[y].emplace_back(x);
  }
  rec(0, -1);
  printf("%d\n", N - root[0]->rmq);
}