2022-08-28

yukicoder No. 901 K-ary εxtrεεmε 別解

解法

木の辺に値が書かれていて、最初はすべて $0$ が書かれているとします。

$i = 1, 2, \dots, k-1$ について、 $x_0 - x_i$ パスに含まれている辺にすべて $1$ を加算すると、 $1$ 以上の数が書かれた辺の重みの合計が答えです。 $0$ が書かれた辺の重みの合計を求め、全体から引くことで求められます。区間加算・区間の最小値とその個数の取得ができる遅延セグメント木を HLD に載せると処理できます。

HLD は $Q$ クエリを通して共通のものを使いたいので、答えを求めた後、 $1$ を加えたパスに $-1$ を加えて値を $0$ に戻す必要があります。

実装

yukicoder.me

#include <bits/stdc++.h>
using namespace std;
const int INF = 10000000;
struct monoid{
  int mn;
  long long sum;
  monoid(): mn(INF), sum(0){
  }
};
monoid op(monoid A, monoid B){
  monoid ans;
  ans.mn = min(A.mn, B.mn);
  if (ans.mn == A.mn){
    ans.sum += A.sum;
  }
  if (ans.mn == B.mn){
    ans.sum += B.sum;
  }
  return ans;
}
struct lazy_segment_tree{
  int N;
  vector<int> lazy;
  vector<monoid> ST;
  lazy_segment_tree(){
  }
  lazy_segment_tree(vector<int> w){
    int N2 = w.size();
    N = 1;
    while (N < N2){
      N *= 2;
    }
    ST = vector<monoid>(N * 2 - 1);
    for (int i = 0; i < N2; i++){
      ST[N - 1 + i].mn = 0;
      ST[N - 1 + i].sum = w[i];
    }
    for (int i = N - 2; i >= 0; i--){
      ST[i] = op(ST[i * 2 + 1], ST[i * 2 + 2]);
    }
    lazy = vector<int>(N * 2 - 1, 0);
  }
  void push(int i){
    if (i < N - 1){
      lazy[i * 2 + 1] += lazy[i];
      lazy[i * 2 + 2] += lazy[i];
    }
    ST[i].mn += lazy[i];
    lazy[i] = 0;
  }
  void range_add(int L, int R, int x, int i, int l, int r){
    push(i);
    if (r <= L || R <= l){
      return;
    } else if (L <= l && r <= R){
      lazy[i] += x;
      push(i);
    } else {
      int m = (l + r) / 2;
      range_add(L, R, x, i * 2 + 1, l, m);
      range_add(L, R, x, i * 2 + 2, m, r);
      ST[i] = op(ST[i * 2 + 1], ST[i * 2 + 2]);
    }
  }
  void range_add(int L, int R, int x){
    range_add(L, R, x, 0, 0, N);
  }
  monoid all(){
    push(0);
    return ST[0];
  }
};
struct heavy_light_decomposition{
  vector<int> p, sz, in, next;
  lazy_segment_tree ST;
  heavy_light_decomposition(vector<int> &p, vector<vector<int>> &c, vector<int> &w): p(p){
    int N = p.size();
    sz = vector<int>(N);
    dfs1(c);
    in = vector<int>(N);
    next = vector<int>(N, 0);
    int t = 0;
    dfs2(c, t);
    vector<int> w2(N, 0);
    for (int i = 0; i < N; i++){
      w2[in[i]] = w[i];
    }
    ST = lazy_segment_tree(w2);
  }
  void dfs1(vector<vector<int>> &c, int v = 0){
    sz[v] = 1;
    for (int &w : c[v]){
      dfs1(c, w);
      sz[v] += sz[w];
      if (sz[w] > sz[c[v][0]]){
        swap(w, c[v][0]);
      }
    }
  }
  void dfs2(vector<vector<int>> &c, int &t, int v = 0){
    in[v] = t;
    t++;
    for (int w : c[v]){
      if (w == c[v][0]){
        next[w] = next[v];
      } else {
        next[w] = w;
      }
      dfs2(c, t, w);
    }
  }
  int lca(int u, int v){
    while (true){
      if (in[u] > in[v]){
        swap(u, v);
      }
      if (next[u] == next[v]){
        return u;
      }
      v = p[next[v]];
    }
  }
  void path_add(int u, int v, int x){
    int w = lca(u, v);
    while (next[u] != next[w]){
      ST.range_add(in[next[u]], in[u] + 1, x);
      u = p[next[u]];
    }
    ST.range_add(in[w] + 1, in[u] + 1, x);
    while (next[v] != next[w]){
      ST.range_add(in[next[v]], in[v] + 1, x);
      v = p[next[v]];
    }
    ST.range_add(in[w] + 1, in[v] + 1, x);
  }
  monoid get(){
    return ST.all();
  }
};
int main(){
  int N;
  cin >> N;
  vector<vector<pair<int, int>>> E(N);
  for (int i = 0; i < N - 1; i++){
    int u, v, w;
    cin >> u >> v >> w;
    E[u].push_back(make_pair(w, v));
    E[v].push_back(make_pair(w, u));
  }
  vector<int> p(N, -1);
  vector<vector<int>> c(N);
  vector<int> pw(N);
  queue<int> q;
  q.push(0);
  while (!q.empty()){
    int v = q.front();
    q.pop();
    for (pair<int, int> e : E[v]){
      int w = e.second;
      if (w != p[v]){
        p[w] = v;
        c[v].push_back(w);
        pw[w] = e.first;
        q.push(w);
      }
    }
  }
  long long sum = 0;
  for (int i = 1; i < N; i++){
    sum += pw[i];
  }
  heavy_light_decomposition HLD(p, c, pw);
  int Q;
  cin >> Q;
  for (int i = 0; i < Q; i++){
    int k;
    cin >> k;
    vector<int> x(k);
    for (int j = 0; j < k; j++){
      cin >> x[j];
    }
    for (int j = 1; j < k; j++){
      HLD.path_add(x[0], x[j], 1);
    }
    cout << sum - HLD.get().sum << endl;
    for (int j = 1; j < k; j++){
      HLD.path_add(x[0], x[j], -1);
    }
  }
}

2022-07-26

ACPC 2021 Day2 J を一般グラフで解く (実装編)

問題解説 AOJ

Nachia さんの考えたアルゴリズムを実装しました。 www.mathenachia.blog

注意

簡単なランダムチェッカーを通しています。
時間計算量については確認していませんが、ACPC 2021 Day2 J を AC することはできました。
下のコードはグラフが入力された場合に答えるコードです。ACPC 2021 Day2 J を AC できるコードは大部分が同じなので掲載しません。以下のリンクから確認してください。 judge.u-aizu.ac.jp

#include <bits/stdc++.h>
using namespace std;
struct extended_block_cut_tree{
  int N, cnt;
  vector<vector<int>> G;
  extended_block_cut_tree(vector<vector<int>> &E){
    N = E.size();
    vector<int> next(N, -1);
    vector<int> d(N, -1);
    vector<int> imos(N, 0);
    for (int i = 0; i < N; i++){
      if (d[i] == -1){
        d[i] = 0;
        dfs1(E, next, d, imos, i);
      }
    }
    cnt = 0;
    G.resize(N + 1);
    vector<bool> used(N, false);
    for (int i = 0; i < N; i++){
      if (d[i] == 0){
        dfs2(E, d, imos, used, cnt, i);
      }
      if (E[i].empty()){
        G[i].push_back(N + cnt);
        G[N + cnt].push_back(i);
        cnt++;
        G.push_back({});
      }
    }
    G.pop_back();
  }
  void dfs1(vector<vector<int>> &E, vector<int> &next, vector<int> &d, vector<int> &imos, int v){
    for (int w : E[v]){
      if (d[w] == -1){
        d[w] = d[v] + 1;
        next[v] = w;
        dfs1(E, next, d, imos, w);
        imos[v] += imos[w];
      } else if (d[w] < d[v] - 1){
        imos[v]++;
        imos[next[w]]--;
      }
    }
  }
  void dfs2(vector<vector<int>> &E, vector<int> &d, vector<int> &imos, vector<bool> &used, int b, int v){
    used[v] = true;
    bool ok = false;
    for (int w : E[v]){
      if (d[w] == d[v] + 1 && !used[w]){
        if (imos[w] > 0){
          if (!ok){
            ok = true;
            G[v].push_back(N + b);
            G[N + b].push_back(v);
          }
          dfs2(E, d, imos, used, b, w);
        } else {
          G[v].push_back(N + cnt);
          G[N + cnt].push_back(v);
          cnt++;
          G.push_back({});
          dfs2(E, d, imos, used, cnt - 1, w);
        }
      }
    }
    if (!ok && d[v] > 0){
      G[v].push_back(N + b);
      G[N + b].push_back(v);
    }
  }
  int size(){
    return G.size();
  }
  vector<int> &operator [](int v){
    return G[v];
  }
};
struct ford_fulkerson{
  struct edge{
    int to, rev, cap;
    edge(int to, int rev, int cap): to(to), rev(rev), cap(cap){
    }
  };
  int N;
  vector<vector<edge>> G;
  ford_fulkerson(int N): N(N), G(N){
  }
  void add_edge(int from, int to){
    G[from].push_back(edge(to, G[to].size(), 1));
    G[to].push_back(edge(from, G[from].size() - 1, 0));
  }
  void max_flow(int s, int t, int F){
    int flow = 0;
    while (flow < F){
      vector<int> pv(N, -1);
      vector<int> pe(N, -1);
      vector<bool> used(N, false);
      used[s] = true;
      queue<int> Q;
      Q.push(s);
      while (!Q.empty()){
        int v = Q.front();
        Q.pop();
        int cnt = G[v].size();
        for (int i = 0; i < cnt; i++){
          int w = G[v][i].to;
          if (!used[w] && G[v][i].cap > 0){
            used[w] = true;
            pv[w] = v;
            pe[w] = i;
            Q.push(w);
          }
        }
      }
      if (!used[t]){
        break;
      }
      for (int v = t; v != s; v = pv[v]){
        G[pv[v]][pe[v]].cap--;
        G[v][G[pv[v]][pe[v]].rev].cap++;
      }
      flow++;
    }
  }
};
int main(){
  int N, M;
  cin >> N >> M;
  vector<vector<int>> E(N);
  for (int i = 0; i < M; i++){
    int u, v;
    cin >> u >> v;
    u--;
    v--;
    E[u].push_back(v);
    E[v].push_back(u);
  }
  extended_block_cut_tree T(E);
  int V = T.size();
  vector<int> p(V, -1);
  vector<int> d(V, 0);
  for (int i = 0; i < V; i++){
    if (p[i] == -1){
      queue<int> Q;
      Q.push(i);
      while (!Q.empty()){
        int v = Q.front();
        Q.pop();
        for (int w : T[v]){
          if (w != p[v]){
            p[w] = v;
            d[w] = d[v] + 1;
            Q.push(w);
          }
        }
      }
    }
  }
  vector<int> bp = {N - 1};
  bool ok = false;
  while (true){
    int v = bp.back();
    if (v == 0){
      ok = true;
      break;
    }
    if (d[v] == 0){
      break;
    }
    bp.push_back(p[v]);
  }
  vector<int> ans(N, 0);
  if (!ok){
    for (int i = 1; i < N - 1; i++){
      ans[i] = N - 3;
    }
  } else {
    int L = bp.size();
    vector<bool> is_art(N, false);
    int art_cnt = 0;
    for (int i = 0; i < L; i++){
      if (1 <= bp[i] && bp[i] < N - 1 && T[bp[i]].size() >= 2){
        is_art[bp[i]] = true;
        art_cnt++;
      }
    }
    vector<vector<pair<int, int>>> edge(V - N);
    for (int i = 0; i < N; i++){
      for (int j : E[i]){
        if (i < j){
          int v;
          if (d[i] >= d[j]){
            v = p[i];
          } else {
            v = p[j];
          }
          edge[v - N].push_back(make_pair(i, j));
        }
      }
    }
    vector<int> id(N);
    for (int i = 1; i < L; i += 2){
      int cnt = 0;
      vector<int> id2;
      for (int j : T[bp[i]]){
        id[j] = cnt;
        id2.push_back(j);
        cnt++;
      }
      if (cnt == 2){
        continue;
      }
      vector<vector<int>> E2(cnt);
      for (pair<int, int> P : edge[bp[i] - N]){
        int u = id[P.first];
        int v = id[P.second];
        E2[u].push_back(v);
        E2[v].push_back(u);
      }
      int s = id[bp[i - 1]];
      int t = id[bp[i + 1]];
      ford_fulkerson G(cnt * 2);
      for (int j = 0; j < cnt; j++){
        G.add_edge(j, cnt + j);
      }
      for (int j = 0; j < cnt; j++){
        for (int k : E2[j]){
          G.add_edge(cnt + j, k);
        }
      }
      G.max_flow(cnt + s, t, 2);
      vector<vector<int>> path;
      for (ford_fulkerson::edge e : G.G[t]){
        if (e.cap > 0 && e.to != cnt + t){
          vector<int> tmp = {t};
          int v = e.to;
          while (v != cnt + s){
            if (v < cnt){
              tmp.push_back(v);
            }
            for (ford_fulkerson::edge e : G.G[v]){
              if (e.cap > 0){
                v = e.to;
                break;
              }
            }
          }
          tmp.push_back(s);
          path.push_back(tmp);
        }
      }
      reverse(path[0].begin(), path[0].end());
      reverse(path[1].begin(), path[1].end());
      for (int j = 0; j < 2; j++){
        int cnt1 = path[1].size();
        vector<bool> is_path1(cnt, false);
        for (int k = 1; k < cnt1 - 1; k++){
          is_path1[path[1][k]] = true;
        }
        vector<vector<int>> E3(cnt);
        for (int u = 0; u < cnt; u++){
          for (int v : E2[u]){
            if (!is_path1[u] && !is_path1[v]){
              E3[u].push_back(v);
            }
          }
        }
        extended_block_cut_tree T2(E3);
        int V2 = T2.size();
        vector<int> p2(V2, -1);
        queue<int> Q2;
        Q2.push(s);
        while (!Q2.empty()){
          int v = Q2.front();
          Q2.pop();
          for (int w : T2[v]){
            if (w != p2[v]){
              p2[w] = v;
              Q2.push(w);
            }
          }
        }
        vector<int> path2;
        path2.push_back(t);
        for (int v = p2[t]; v != s; v = p2[v]){
          if (v < cnt && T2[v].size() >= 2){
            path2.push_back(v);
          }
        }
        path2.push_back(s);
        reverse(path2.begin(), path2.end());
        path[0] = path2;
        int cnt0 = path[0].size();
        for (int k = 0; k < cnt0 - 1; k++){
          int u = path[0][k];
          int v = path[0][k + 1];
          bool ee = false;
          for (int w : E2[u]){
            if (w == v){
              ee = true;
            }
          }
          if (!ee){
            E2[u].push_back(v);
            E2[v].push_back(u);
          }
        }
        vector<bool> gray(cnt, true);
        for (int k = 0; k < cnt0; k++){
          gray[path[0][k]] = false;
        }
        for (int k = 0; k < cnt1; k++){
          gray[path[1][k]] = false;
        }
        vector<bool> re(cnt, false);
        vector<bool> used2(cnt, false);
        for (int k = 0; k < cnt; k++){
          if (gray[k] && !used2[k]){
            used2[k] = true;
            bool blue = false;
            queue<int> Q;
            Q.push(k);
            vector<int> cc;
            while (!Q.empty()){
              int v = Q.front();
              Q.pop();
              cc.push_back(v);
              for (int w : E2[v]){
                if (gray[w] && !used2[w]){
                  used2[w] = true;
                  Q.push(w);
                } else if (is_path1[w]){
                  blue = true;
                }
              }
            }
            if (!blue){
              for (int v : cc){
                re[v] = true;
              }
            }
          }
        }
        for (int k = 0; k < cnt; k++){
          if (re[k]){
            E2[k].clear();
          } else {
            vector<int> tmp;
            for (int v : E2[k]){
              if (!re[v]){
                tmp.push_back(v);
              }
            }
            E2[k] = tmp;
          }
        }
        swap(path[0], path[1]);
      }
      vector<int> type(cnt, -1);
      for (int v : path[0]){
        type[v] = 0;
      }
      for (int v : path[1]){
        type[v] = 1;
      }
      type[s] = 2;
      type[t] = 2;
      int cnt0 = path[0].size();
      vector<int> pos0(cnt, -1);
      for (int j = 0; j < cnt0; j++){
        pos0[path[0][j]] = j;
      }
      int cnt1 = path[1].size();
      vector<int> pos1(cnt, -1);
      for (int j = 0; j < cnt1; j++){
        pos1[path[1][j]] = j;
      }
      vector<pair<int, int>> E3;
      vector<bool> used(cnt, false);
      for (int j = 0; j < cnt; j++){
        if (!used[j] && type[j] == -1){
          used[j] = true;
          vector<int> id;
          vector<int> p0, p1;
          queue<int> Q;
          Q.push(j);
          while (!Q.empty()){
            int v = Q.front();
            Q.pop();
            id.push_back(v);
            for (int w : E2[v]){
              if (!used[w] && type[w] == -1){
                used[w] = true;
                Q.push(w);
              } else if (type[w] == 0){
                p0.push_back(w);
              } else if (type[w] == 1){
                p1.push_back(w);
              } else if (type[w] == 2){
                p0.push_back(w);
                p1.push_back(w);
              }
            }
          }
          for (int v : p0){
            for (int w : p1){
              E3.push_back(make_pair(pos0[v], pos1[w]));
            }
          }
        }
      }
      vector<int> mx1(cnt0, cnt1 - 2);
      vector<int> mn1(cnt0, 1);
      vector<int> mx2(cnt1, cnt0 - 2);
      vector<int> mn2(cnt1, 1);
      for (pair<int, int> P : E3){
        int u = P.first;
        int v = P.second;
        if (u > 0){
          mx1[u - 1] = min(mx1[u - 1], v);
        }
        if (u < cnt0 - 1){
          mn1[u + 1] = max(mn1[u + 1], v);
        }
        if (v > 0){
          mx2[v - 1] = min(mx2[v - 1], u);
        }
        if (v < cnt1 - 1){
          mn2[v + 1] = max(mn2[v + 1], u);
        }
      }
      for (int j = cnt0 - 2; j >= 0; j--){
        mx1[j] = min(mx1[j], mx1[j + 1]);
      }
      for (int j = 0; j < cnt0 - 1; j++){
        mn1[j + 1] = max(mn1[j + 1], mn1[j]);
      }
      for (int j = cnt1 - 2; j >= 0; j--){
        mx2[j] = min(mx2[j], mx2[j + 1]);
      }
      for (int j = 0; j < cnt1 - 1; j++){
        mn2[j + 1] = max(mn2[j + 1], mn2[j]);
      }
      for (int j = 1; j < cnt0 - 1; j++){
        ans[id2[path[0][j]]] += max(0, mx1[j] - mn1[j] + 1);
      }
      for (int j = 1; j < cnt1 - 1; j++){
        ans[id2[path[1][j]]] += max(0, mx2[j] - mn2[j] + 1);
      }
    }
    for (int i = 1; i < N - 1; i++){
      ans[i] += art_cnt;
      if (is_art[i]){
        ans[i] = N - 3;
      }
    }
  }
  for (int i = 1; i < N - 1; i++){
    cout << ans[i];
    if (i < N - 2){
      cout << ' ';
    }
  }
  cout << endl;
}

2022-07-14

未来の AtCoder

日時	出来事
2038/01/09 12:14	practice contest が終了する。
2728/05/29 22:44	AtCoder Library Practice Contest の順位表が凍結される。
3020/02/29 21:00	AGC042 が開始する。
3020/03/01 01:00	AGC042 が終了する。
3020/09/27 22:31	AtCoder Library Practice Contest が終了する。
3021/12/17 02:00	アルゴリズムと数学　演習問題集が終了する。
3030/10/03 21:00	ACL Contest 2 が開始する。
3030/10/03 23:30	ACL Contest 2 が終了する。
4017/12/13 21:00	APG4b が終了する。
4018/03/14 21:00	AtCoder Beginners Selection が終了する。
5021/07/11 19:00	競プロ典型 90 問が終了する。

2021-12-18

Stage 6: Grand Prix of EDG (2021-11-14)

問題文 Opencup

jコンテストページ

official.contest.yandex.ru

問題概要

問題 A: A Hero Named Magnus

実行時間制限: 1 秒 / メモリ制限: 512 Mb

$n$ ( $n$ は奇数) 回試合を行うことを考える。 $1$ 試合目から $x-1$ 試合目までは $50 \%$ の確率で試合に勝ち、 $x$ 試合目以降は必ず試合に勝てるとき、 $n$ 回試合を行ったあと勝った試合が負けた試合より必ず多くなるようにするとき、 $n$ の最小値を求めよ。ただし、 $T$ 個のテストケースが与えられるので、すべて答えよ。

入力は以下の制約を満たす。

$1 \leq T \leq 10 ^ 5$
$1 \leq x \leq 2 \times 10 ^ 9$

問題 B: A Plus B Problem

実行時間制限: 3 秒 / メモリ制限: 512 Mb

縦 $3$ 行、横 $n$ 列に数字を表示する機械がある。 $1$ 行目と $2$ 行目の数字は自由に変更することができるが、 $3$ 行目の数字は常に $1$ 行目と $2$ 行目に表示された数字をそれぞれ $n$ 桁の整数として見たときのそれらの和の下 $n$ 桁を表示する。

$q$ 個のクエリが与えられる。 $i$ 番目のクエリでは、整数 $r _ i, c _ i, d _ i$ が与えられるので、 $r _ i$ 行目 $c _ i$ 列目の数字を $d _ i$ に変更した後、 $3$ 行目 $c _ i$ 列目に表示されている数字と表示される数字が変化した箇所の個数を出力せよ。

入力は以下の制約を満たす。

$1 \leq n, q \leq 10 ^ 6$
$1 \leq r _ i \leq 2$
$1 \leq c _ i \leq n$
$0 \leq d _ i \leq 9$

問題 C: AC Automaton

実行時間制限: 13 秒 / メモリ制限: 512 Mb

頂点 $1$ を根とする $n$ 頂点の根付き木が与えられる。頂点 $i$ の親は $p _ i$ である。また、各頂点には文字 $s _ i$ が書かれている。ただし、 $s _ i$ は A, C, ? のいずれかである。

$q$ 個のクエリが与えられる。各クエリでは整数 $x$ と文字 $y$ が与えられるので、頂点 $x$ に書かれた文字を $y$ に変更せよ。次に、? が書かれた各頂点に書かれた文字を A または C に変更したとき、頂点 $x$ が頂点 $y$ の先祖で頂点 $x, y$ にそれぞれ A, C が書かれているような頂点の組 $(x, y)$ の個数の最大値を求めよ。ただし、この変更は実際は行わないものとする。

入力は以下の制約を満たす。

$1 \leq n, q \leq 300000$
$1 \leq p _ i \lt i$
$1 \leq x \leq n$
$y$ は A, C, ? のいずれかである。

問題 D: Assumption is All You Need

実行時間制限: 1 秒 / メモリ制限: 512 Mb

長さ $n$ の順列 $A, B$ が与えられる。 $A$ に以下の操作を繰り返して $B$ に変換する手順を示すか、そのような手順が存在しないことを報告せよ。

$1 \leq x \lt y \leq n, A _ x > A _ y$ なる整数 $x, y$ を選び、 $A _ x$ と $A _ y$ を交換する。

ただし、 $T$ 個のテストケースが与えられるので、すべて答えよ。

入力は以下の制約を満たす。

すべてのテストケースに対する $n$ の和は $2021$ 以下である。

問題 E: Buy and Delete

実行時間制限: 2 秒 / メモリ制限: 512 Mb

$n$ 頂点の有向グラフ $G$ がある。最初、 $G$ に辺はない。

アリスとボブがゲームを行う。アリスは $c$ ドルを持っていて、 $m$ 種類の辺を買うことができる。 $i$ 番目の辺は $p _ i$ ドルであり、買うと $G$ の頂点 $u _ i$ から頂点 $v _ i$ に有向辺が張られる。その後、ボブは以下の操作を繰り返し $G$ を辺がない状態にする。

$G$ の辺の部分集合 $S$ であって閉路を含まないものを選び、 $S$ に属する辺をすべて削除する。

ボブは操作の回数を最大化しようとし、アリスは操作の回数を最小化しようとするとき、ボブが操作を行う回数を求めよ。

入力は以下の制約を満たす。

$2 \leq n \leq 2000$
$1 \leq m \leq 5000$
$1 \leq c \leq 10 ^ 9$
$1 \leq u _ i, v _ i \leq n$
$u _ i \neq v _ i$
$1 \leq p _ i \leq 100000$

問題 F: Illuminations II

実行時間制限: 2 秒 / メモリ制限: 512 Mb

二つの凸多角形があり、一方はもう一方の内部に完全に含まれている。外側の凸多角形は $n$ 角形、内側の凸多角形は $m$ 角形である。

外側の凸多角形の辺上のランダムな点にライトを設置するとき、内側の凸多角形の辺のうちライトで照らされる部分の長さの期待値を求めよ。

想定解答との絶対誤差または相対誤差が $10 ^ {-9}$ 以下であれば正解として扱われる。

入力は以下の制約を満たす。

$3 \leq n, m \leq 2 \times 10 ^ 5$
頂点の座標は整数で絶対値が $10 ^ 9$ 以下である。

問題 G: Occupy The Cities

実行時間制限: 1 秒 / メモリ制限: 512 Mb

$n$ 個の都市が一直線上に順番に並んでいて、そのうち $1$ 個以上は占領されている。長さ $n$ の文字列 $s$ が与えられ、 $s$ の $i$ 文字目が 1 のときは都市 $i$ が最初に占領されていること、`0 のときは都市 $i$ が最初に占領されていないことを示す。

以下の操作を繰り返し、すべての都市を占領された状態にしたい。

占領されているそれぞれの都市が、隣接する占領されていない都市を $1$ つまで選び、その都市を占領された状態にする。

操作の最小回数を求めよ。ただし、 $T$ 個のテストケースが与えられるので、すべて答えよ。

入力は以下の制約を満たす。

すべてのテストケースに対する $n$ の和は $10 ^ 6$ 以下である。
$s$ は 0 と 1 のみからなる長さ $n$ の文字列である。
$s$ には 1 が $1$ つ以上含まれる。

問題 H: Popcount Words

実行時間制限: 1 秒 / メモリ制限: 512 Mb

区間 $[l, r ]$ に対し、文字列 $w(l, r)$ を以下のように定義する。

$w(l, r) = s _ l s _ {l + 1} \cdots s _ r$ である。ただし、 $s _ i$ は $i$ を $2$ 進数で表したときの $1$ の個数が偶数ならば 0、奇数ならば 1 である。

$n$ 個の区間 $[l _ 1, r _ 1 ], [l _ 2, r _ 2 ], \cdots, [l _ n, r _ n ]$ が与えられる。 $S = w(l _ 1, r _ 1) + w(l _ 2, r _ 2) + \cdots + w(l _ n, r _ n)$ とする。ただし、 $+$ は文字列の連結を表す。

$q$ 個のクエリが与えられる。各クエリでは文字列 $p$ が与えられるので、 $S$ のうち $p$ が部分文字列として出現する回数を出力せよ。

入力は以下の制約を満たす。

$1 \leq n, q \leq 100000$
$1 \leq l _ i \leq r _ i \leq 10 ^ 9$
$p$ は 0 と 1 のみからなる。
すべてのクエリに対する $p$ の長さの和は $500000$ 以下である。

問題 I: PTSD

実行時間制限: 1 秒 / メモリ制限: 512 Mb

$n$ 人の人 $1,2, \cdots, n$ がいる。 $n$ 文字の 0 または 1 からなる文字列 $s$ が与えられ、 $s$ の $i$ 文字目が 1 のときは人 $i$ が PTSD を持っていること、0 のときは持っていないことを示す。

$n$ 人を何個かのグループに分けるとき、各グループのうち $2$ 番目に番号が大きい人で PTSD を持っている人の番号の総和としてありうる最大値を求めよ。ただし、 $T$ 個のテストケースが与えられるので、すべて答えよ。

入力は以下の制約を満たす。

すべてのテストケースに対する $n$ の和は $10 ^ 6$ 以下である。
$s$ は 0 と 1 のみからなる長さ $n$ の文字列である。
$s$ には 1 が $1$ つ以上含まれる。

問題 J: Suffix Automaton

実行時間制限: 6 秒 / メモリ制限: 512 Mb

文字列 $S$ のすべての異なる部分文字列を長さの昇順にソートし、同じ長さのものは辞書順に並べた列を $A$ とする。

$Q$ 個のクエリが与えられる。各クエリでは整数 $k$ が与えられるので、 $A$ の $k$ 番目の文字列が $S$ に現れる最も左側の区間の左端と右端の位置を求めよ。ただし、 $k$ が $A$ の長さより大きい場合は、-1 -1 と出力せよ。

入力は以下の制約を満たす。

$1 \leq |S| \leq 10 ^ 6$
$1 \leq Q \leq 10 ^ 6$
$1 \leq k \leq 10 ^ {12}$

問題 K: Tax

実行時間制限: 2 秒 / メモリ制限: 512 Mb

$n$ 個の都市があり、 $m$ 本の道路で結ばれている。道路を用いてどの $2$ つの都市の間も行き来することができる。 $i$ 番目の道路は都市 $u _ i$ と都市 $v _ i$ を結び、会社 $c _ i$ によって管理されている。また、長さ $m$ の整数の列 $m$ が与えられ、会社 $t$ が管理している道路を $k$ 回目に通るときは $k \times w _ t$ ドルを支払う必要がある。 $k = 2, 3, \cdots, n$ のそれぞれに対し、都市 $1$ から都市 $k$ へ行くときに最小で何ドル必要か求めよ。

入力は以下の制約を満たす。

$2 \leq n \leq 50$
$n - 1 \leq m \leq \displaystyle{\frac{n(n-1)}{2}}$
$1 \leq w _ i \leq 1000$
$1 \leq u _ i, v _ i \leq n$
$u _ i \neq v _ i$
$1 \leq c _ i \leq m$
どの $2$ つの都市も $1$ 本以下の道路で結ばれている。
道路を用いてどの $2$ つの都市の間も行き来することができる。

問題 L: Wiring Engineering

実行時間制限: 8 秒 / メモリ制限: 512 Mb

$n$ 個のビルがあり、 $i$ 番目のビルは座標 $(i, 1)$ にある。また、 $n$ 個の通信塔があり、 $i$ 番目の通信塔は座標 $(i, -1)$ にある。

$q$ 個のクエリが与えられる。 $i$ 番目のクエリでは、整数 $a _ i, b _ i, c _ i, d _ i$ が与えられるとき、区間 $[ a _ i, b _ i ]$ のビルと $[ c _ i, d _ i ]$ の通信塔の間に以下の条件を満たすように何本かの電線を張ったとき、最大何ドル得られるか求めよ。

ビル $i$ と通信塔 $j$ を電線で結ぶと $w _ {i, j}$ ドルが得られる。ただし、電線はビル $i$ と通信塔 $j$ を結ぶ線分である。
ビル $i$ に $1$ 本以上の電線を張るとき、 $u _ i$ ドルを支払う。
通信塔 $i$ に $1$ 本以上の電線を張るとき、 $v _ i$ ドルを支払う。
$2$ 本以上の電線がその端点以外で交わってはならない。

入力は以下の制約を満たす。

$1 \leq n \leq 500$
$1 \leq q \leq 300000$
$1 \leq u _ i \leq 10000$
$1 \leq v _ i \leq 10000$
$1 \leq w _ {i, j} \leq 10000$
$1 \leq a _ i \leq b _ i \leq n$
$1 \leq c _ i \leq d _ i \leq n$

問題文

問題 A: A Hero Named Magnus

https://official.contest.yandex.ru/opencupXXII/contest/31241/problems/A/

問題 B: A Plus B Problem

https://official.contest.yandex.ru/opencupXXII/contest/31241/problems/B/

問題 C: AC Automaton

https://official.contest.yandex.ru/opencupXXII/contest/31241/problems/C/

問題 D: Assumption is All You Need

https://official.contest.yandex.ru/opencupXXII/contest/31241/problems/D/

問題 E: Buy and Delete

https://official.contest.yandex.ru/opencupXXII/contest/31241/problems/E/

問題 F: Illuminations II

https://official.contest.yandex.ru/opencupXXII/contest/31241/problems/F/

問題 G: Occupy The Cities

https://official.contest.yandex.ru/opencupXXII/contest/31241/problems/G/

問題 H: Popcount Words

https://official.contest.yandex.ru/opencupXXII/contest/31241/problems/H/

問題 I: PTSD

https://official.contest.yandex.ru/opencupXXII/contest/31241/problems/I/

問題 J: Suffix Automaton

https://official.contest.yandex.ru/opencupXXII/contest/31241/problems/J/

問題 K: Tax

https://official.contest.yandex.ru/opencupXXII/contest/31241/problems/K/

問題 L: Wiring Engineering

https://official.contest.yandex.ru/opencupXXII/contest/31241/problems/L/

2021-11-29

Stage 5: Grand Prix of Siberia (2021-11-07)

問題文 Opencup

コンテストページ

official.contest.yandex.ru

問題概要

問題 1: Polesov and Work

実行時間制限: 3 秒 / メモリ制限: 256 Mb

整数 $a, b$ と正の整数 $R$ が与えられる。円 $x ^ 2+y ^ 2 \leq R ^ 2$ 内の格子点 $(x, y)$ に対し、 $ax+by$ の最大値を求めよ。ただし、 $T$ 個のテストケースが与えられるので、すべて答えよ。

入力は以下の制約を満たす。

$1 \leq T \leq 1000$
$- 10 ^ 9 \leq a, b \leq 10 ^ 9$
$1 \leq R \leq 10 ^ 9$

問題 2: Orienteering

実行時間制限: 5 秒 / メモリ制限: 256 Mb

座標平面上に $N$ 個のチェックポイントがあり、 $i \ (1 \leq i \leq N)$ 番目のチェックポイントは点 $(x _ i, y _ i)$ にある。それぞれのチェックポイントは、その位置から距離 $R$ 以内の点を訪れたとき、通過したとみなす。

座標平面上の任意の点から開始し、 $N$ 個のチェックポイントを順に通過したい。ただし、途中で他のチェックポイントを通過してもよいが、それらは通過したとみなさない。このとき、移動距離の最小値を求めよ。

想定解答との絶対誤差または相対誤差が $0.01$ 以下であれば正解として扱われる。

入力は以下の制約を満たす。

$1 \leq N \leq 100$
$1 \leq R \leq 10 ^ 9$
$- 10 ^ 9 \leq x _i, y _ i \leq 10 ^ 9 \ (1 \leq i \leq N)$

問題 3: Dice

実行時間制限: 2 秒 / メモリ制限: 256 Mb

それぞれの面に $1, 2, \ldots, f$ と書かれた $f$ 個の面があるサイコロが $n$ 個ある。これらのサイコロを振り、出た目の数の合計を計算し、さらに $m$ を加算した。結果が $S$ となることがあか判定せよ。ただし、 $B$ 個のテストケースが与えられるので、すべて答えよ。

入力は以下の制約を満たす。

$1 \leq B \leq 10 ^ 5$
$1 \leq S \leq 300$
$1 \leq n \leq 10$
$2 \leq f \leq 20$
$0 \leq m \leq 10$

問題 4: Numeral Systems

実行時間制限: 3 秒 / メモリ制限: 256 Mb

先頭が $0$ でない数字のみからなる $K$ 文字の文字列であって、 $10$ 進数として見たときの値を $X$ 、 $16$ 進数として見たときの値を $Y$ としたとき、 $X \gt D$ であり $Y$ が $X-D$ で割り切れるようなものを、昇順にすべて列挙せよ。ただし、 $T$ 個のテストケースが与えられるので、すべて答えよ。

入力は以下の制約を満たす。

$1 \leq T \leq 100$
$2 \leq K \leq 15$
$0 \leq D \leq 10 ^ 6$

問題 5: Hockey

実行時間制限: 1 秒 / メモリ制限: 256 Mb

ゴールキーパーを除き各チーム $5$ 人で $60$ 分間ホッケーの試合をする。

試合を行っているそれぞれの選手は、ペナルティを受けることがある。ペナルティにはマイナーペナルティとメジャーペナルティの $2$ 種類があり、ペナルティを受けた選手はそれぞれ $2, 5$ 分間試合から外れる。また、一方のチームが相手のチームより試合を行っている人数が少なく、相手のチームがゴールをした場合、そのチームにマイナーペナルティにより試合から外れている選手がいれば、それらのうち最も早くにペナルティを受けた選手 $1$ 人が試合に戻る。

$60$ 分間の間に発生したゴールとペナルティの情報が時間の順に $0.1$ 秒の位まで $N$ 個与えられる。ただし、ゴールが発生した時刻の $0.1$ 秒の位は必ず $0$ 以外であり、ペナルティが発生した時刻の $0.1$ 秒の位は必ず $0$ であることが保証される。

試合中のある時点について、二つのチームで試合を行っている選手の人数がそれぞれ $a$ 人、 $b$ 人であるとき、試合の形式が $a$ 対 $b$ であるという。 $60$ 分間でそれぞれの試合形式が発生していた期間の長さを、一度以上発生した試合形式それぞれについて出力せよ。出力の順番は問わない。ただし、少なくとも一方のチームで試合を行っている選手の人数が $5$ 人未満だった期間が必ず存在することが保証される。

入力は以下の制約を満たす。

$0 \leq N \leq 1000$

問題 6: Days of The Week

実行時間制限: 1 秒 / メモリ制限: 256 Mb

$M$ 個の宇宙があり、それぞれの宇宙には $1$ つの曜日 (月曜日、火曜日、水曜日、木曜日、金曜日、土曜日、日曜日のうちの $1$ つ) が定められている。それぞれの宇宙の現在の曜日が与えられる。

$N$ 個のスイッチがある。それぞれのスイッチにはある宇宙の集合が対応しており、そのスイッチを押すとそれらの宇宙の曜日がそれぞれ $1$ 日分進む。スイッチは任意の順番で何度でも押すことができる。各宇宙の曜日の組み合わせ $7 ^ M$ 個のうち、スイッチを何度か押すことで作ることのできないものが存在するか判定せよ。存在しない場合は NO と出力し、存在する場合は YES と出力した後そのような組み合わせを $1$ つ出力せよ。ただし、 $T$ 個のテストケースが与えられるので、すべて答えよ。

入力は以下の制約を満たす。

$1 \leq T \leq 500$
$1 \leq N \leq 500$
$1 \leq M \leq 500$

問題 7: Balls

実行時間制限: 3 秒 / メモリ制限: 255 Mb

青玉と赤玉をそれぞれ何個か用意し、アリスとボブがゲームを行う。

アリスから始めて、 $2$ 人が交互に玉を $1$ つ取る。ただし、アリスは残っている玉すべてを等確率で取り、ボブは必ず赤玉 $1$ つを取る。また、どちらの手番であるかに関わらず、残っている青玉が $0$ 個になったらアリスが勝ち、残っている青玉の個数が赤玉の個数より多くなったらボブが勝つ。

ゲームを $G$ 回行う。それぞれのゲームでは、青玉と赤玉の合計個数 $C$ が指定されるので、アリスが勝つ確率と $0.5$ の差の絶対値がなるべく小さくなるように青玉と赤玉を用意したい。このとき、用意すべき青玉の個数を出力せよ。

入力は以下の制約を満たす。

$1 \leq G \leq 10 ^ 5$
$2 \leq C \leq 2 \times 10 ^ 5$

問題 8: Romualdych and Remainders

実行時間制限: 2 秒 / メモリ制限: 256 Mb

整数 $a, b, r$ が与えられる。 $a \leq x \leq b, x \bmod y = r$ を満たす整数の組 $(x, y)$ が存在するか判定せよ。存在しない場合は -1 -1 と出力し、存在する場合はそのような組み合わせのうち $x$ が最も小さいものを $1$ つ出力せよ。ただし、 $T$ 個のテストケースが与えられるので、すべて答えよ。

入力は以下の制約を満たす。

$1 \leq T \leq 200000$
$0 \leq a \leq b \leq 10 ^ {18}$
$0 \leq r \leq 10 ^ {18}$

問題 9: Polynomials

実行時間制限: 3 秒 / メモリ制限: 256 Mb

黒板の左側に $N$ 個の多項式が、右側に $M$ 個の多項式が書かれている。各多項式の次数 $K$ と係数 $a _ 0, a _ 1, \ldots, a _ K$ が与えられる。

黒板の右側に書かれているそれぞれの多項式について、黒板の左側に書かれている多項式を $1$ つ選び、以下の $2$ 種類の操作を繰り返し適用してその多項式と一致するようにするときの、操作回数の最小値を求めよ。

選んだ多項式をそれを微分したものに置き換える。
選んだ多項式をそれを積分に任意の実数を積分定数として加えたものに置き換える。

ただし、操作は黒板の右側に書かれているそれぞれの多項式について独立して考えるものとする。

入力は以下の制約を満たす。

$1 \leq N, M \leq 10 ^ 5$
$-10 ^ 9 \leq a _ i \leq 10 ^ 9$
黒板の左側に書かれている多項式の次数の合計は $10 ^ 5$ 以下である。
黒板の右側に書かれている多項式の次数の合計は $10 ^ 5$ 以下である。

問題 10: Find The Vault

実行時間制限: 6 秒・15 秒 / メモリ制限: 512 Mb

$R \times C$ の #, ., _ からなるグリッド ( $X$ とする) と $A \times B$ の #, ., _ からなるグリッド ( $Y$ とする) が与えられる。 $X$ の $A \times B$ の部分長方形であって、その各マスが以下の条件を満たすものを全て列挙し、それぞれの左上のマスの位置を出力せよ。

そのマスに対応する $Y$ のマスが # であるならば、その $X$ のマスは . ではない。
そのマスに対応する $Y$ のマスが . であるならば、その $X$ のマスは # ではない。

入力は以下の制約を満たす。

$1 \leq R, C \leq 2000$
$1 \leq A \leq R$
$1 \leq B \leq C$

問題 11: Captivating Process

実行時間制限: 4 秒 / メモリ制限: 512 Mb

長さ $N$ の数列 $f, g$ が与えられる。 $Q$ 個のクエリが与えられるので、すべて答えよ。

各クエリでは $1$ 以上 $N$ 以下の整数 $x, y$ が与えられ、以下の操作を繰り返す。

$x=y$ ならば操作を終了する。
そうでないならば、 $x$ を $f _ x$ で、 $y$ を $g _ y$ で置き換える。

操作が有限回の繰り返しで終了するなら YES、そうでないなら NO と出力せよ。

入力は以下の制約を満たす。

$1 \leq N, Q \leq 10 ^ 5$
$1 \leq f _ i, g _ i \leq N$
$1 \leq x, y \leq N$

問題文

問題 1: Polesov and Work

https://official.contest.yandex.ru/opencupXXII/contest/31145/problems/1/

問題 2: Orienteering

https://official.contest.yandex.ru/opencupXXII/contest/31145/problems/2/

問題 3: Dice

https://official.contest.yandex.ru/opencupXXII/contest/31145/problems/3/

問題 4: Numeral Systems

https://official.contest.yandex.ru/opencupXXII/contest/31145/problems/4/

問題 5: Hockey

https://official.contest.yandex.ru/opencupXXII/contest/31145/problems/5/

問題 6: Days of The Week

https://official.contest.yandex.ru/opencupXXII/contest/31145/problems/6/

問題 7: Balls

https://official.contest.yandex.ru/opencupXXII/contest/31145/problems/7/

問題 8: Romualdych and Remainders

https://official.contest.yandex.ru/opencupXXII/contest/31145/problems/8/

問題 9: Polynomials

https://official.contest.yandex.ru/opencupXXII/contest/31145/problems/9/

問題 10: Find The Vault

https://official.contest.yandex.ru/opencupXXII/contest/31145/problems/10/

問題 11: Captivating Process

https://official.contest.yandex.ru/opencupXXII/contest/31145/problems/11/

2021-11-08

ABC226 G: The baggage

問題解説 AtCoder

atcoder.jp

公式解説とは異なる解法で解きました。

解法

荷物の重さの合計が体力の合計より大きいとき答えは明らかに No なので、以後、荷物の重さの合計は体力の合計以下であるとします。このとき、重さ $2$ 以上の荷物をすべて割り当てることができれば、重さ $1$ の荷物も必ず割り当てられるので、重さ $2$ 以上の荷物のみ考えます。

仮に重さ $3$ 以上の荷物がないと仮定すると、割り当てられる重さ $2$ の荷物の個数は最大で $B _ 2+B _ 3+2B _ 4+2B _ 5$ 個となります。この値を $X$ とおくと、重さ $2$ の荷物を割り当てることができるためには $X \geq A _ 2$ となればよいので、重さ $3$ 以上の荷物を加えていったときの $X$ の値を最大化すること、つまり $X$ の値の減少量を最小化することを考えます。

重さ $3$ 以上の荷物は $1$ 人につき $1$ 個しか持つことができません。重さ $3$ の荷物が体力 $3$ または $5$ の人に割り当てられたとき $X$ は $1$ 減少し、重さ $3$ の荷物が体力 $4$ の人に割り当てられたとき、また、重さ $4$ 以上の荷物がそれ以上の体力の人に割り当てられたとき、 $X$ は $2$ 減少します。よって、 $X$ の減少量の最小値は以下のように求めることができます。

の頂点からなる有向グラフを考え、以下のように辺を張ります。
- 頂点 $s$ から $a _ 3, a _ 4, a _ 5$ にそれぞれ容量 $A _ 3, A _ 4, A _ 5$ 、コスト $0$ の辺を張る。
- 頂点 $a _ 3$ から $b _ 3$ と $b _ 5$ にそれぞれ容量 $\infty$ 、コスト $1$ の辺を張る。
- 頂点 $a _ 3$ から $b _ 4$ 、 $a _ 4$ から $b _ 4$ 、 $a _ 4$ から $b _ 5$ 、 $a _ 5$ から $b _ 5$ にそれぞれ容量 $\infty$ 、コスト $2$ の辺を張る。
- 頂点 $b _ 3, b _ 4, b _ 5$ から $t$ にそれぞれ容量 $B _ 3, B _ 4, B _ 5$ 、コスト $0$ の辺を張る。
このグラフ上で頂点 $s$ から $t$ に最小費用流を流します。流量が $A _ 3+A _ 4+A _ 5$ に等しい場合 $X$ の減少量の最小値はコストの合計値に等しく、満たない場合割り当ては不可能です。

実装

atcoder.jp

#include <bits/stdc++.h>
#include <atcoder/mincostflow>
using namespace std;
using namespace atcoder;
const long long INF = 1000000000000000000;
int main(){
  int T;
  cin >> T;
  for (int i = 0; i < T; i++){
    vector<long long> A(6);
    for (int j = 1; j <= 5; j++){
      cin >> A[j];
    }
    vector<long long> B(6);
    for (int j = 1; j <= 5; j++){
      cin >> B[j];
    }
    long long SA = A[1] + A[2] * 2 + A[3] * 3 + A[4] * 4 + A[5] * 5;
    long long SB = B[1] + B[2] * 2 + B[3] * 3 + B[4] * 4 + B[5] * 5;
    if (SA > SB){
      cout << "No" << endl;
    } else {
      long long cnt = B[2] + B[3] + B[4] * 2 + B[5] * 2;
      mcf_graph<long long, long long> G(8);
      G.add_edge(0, 1, A[3], 0);
      G.add_edge(0, 2, A[4], 0);
      G.add_edge(0, 3, A[5], 0);
      G.add_edge(1, 4, INF, 1);
      G.add_edge(1, 5, INF, 2);
      G.add_edge(1, 6, INF, 1);
      G.add_edge(2, 5, INF, 2);
      G.add_edge(2, 6, INF, 2);
      G.add_edge(3, 6, INF, 2);
      G.add_edge(4, 7, B[3], 0);
      G.add_edge(5, 7, B[4], 0);
      G.add_edge(6, 7, B[5], 0);
      pair<long long, long long> F = G.flow(0, 7);
      if (F.first < A[3] + A[4] + A[5]){
        cout << "No" << endl;
      } else {
        cnt -= F.second;
        if (A[2] > cnt){
          cout << "No" << endl;
        } else {
          cout << "Yes" << endl;
        }
      }
    }
  }
}

2021-11-06

ICPC 参加記ではありません

のいみさんが言っていたので

誰か参加記まとめて
— のいみ (@noimi_kyopro) 2021年11月6日