Stage 4: Grand Prix of Korea (2021/10/24 17:00-22:00)

コンテストページ

official.contest.yandex.ru

問題概要

A 問題: Automatic Sprayer 2

実行時間制限: 2 秒 / メモリ制限: 1 GB

の各成分が非負整数の行列 がある。 から、 の行列 を以下のように作った。

• 

が与えられるので、 としてありうるものを つ出力せよ。

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

• 
• 
• 条件を満たす行列 で各成分の和が 以下であるものが存在する。

B 問題: Cilantro

実行時間制限: 0.5 秒 / メモリ制限: 1 GB

Y と N のみからなる長さ の文字列 が与えられる。

スタック を用意し、 の各文字について以下の操作を順に行う。

• の先頭の文字を削除しそれを に push する。
• を pop する。ただしこのとき取り出す文字は に一致しなければならない。

操作 で取り出した文字が に対応することがありうるような整数 をすべて列挙し、それらの和を答えよ。ただし、操作を行うことができない場合は と出力せよ。

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

• 
• の長さは で Y と N のみからなる。

C 問題: Equivalent Pipelines

実行時間制限: 3 秒 / メモリ制限: 1 GB

頂点の辺に重みが付いた木 が与えられる。

木 の異なる頂点 について、 を、頂点 を結ぶパス内の辺の重みの最小値とする。また、 つの木 が を満たすとき、木 は同等であるという。

各 について、木 が木 と同等であるような最小の を出力せよ。

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

• 
• 
• 
• 辺の重みは 以上 以下

D 問題: Flowerbed Redecoration

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

行 列のグリッドがあり、各マスには大文字のアルファベットが書かれている。

について、以下の操作を行う。

• マス を左上とする正方形の各マスの文字を、正方形を時計回りに 度回転させた位置に移動させる。

操作を行った後のグリッドの各マスの文字を出力せよ。

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

• 
• 
• 
• 
• 
• 

E 問題: Goose Coins

実行時間制限: 3 秒 / メモリ制限: 1 GB

種類のコインがあり、 番目のコインの価値は 円、重さは である。 に対し、 は の倍数である。各コインは無限に存在する。

ちょうど 枚のコインを使ってちょうど 円を払うとき、コインの重さの合計の最小値と最大値を出力せよ。ただし、ちょうど 円を払うことができないとき、 と出力せよ。

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

• 
• 
• 
• 
• に対し、 は の倍数である。

F 問題: Hedgehog Graph

実行時間制限: 5 秒 / メモリ制限: 1 GB

の頂点の有向グラフ がある。 の各頂点の出次数は であり、 は閉路を つだけ持ちその頂点数は 以上である。また、 の各辺 に対し、 はこの閉路に含まれる。

以下のクエリを 回まで投げることができる。

• の頂点 と 以上 以下の整数 x を出力する。頂点 から辺に沿って 回移動した後の頂点が与えられる。

の閉路の頂点数を求めよ。ただし、 個のテストケースが与えられるので、すべて答えよ。

G 問題: Lamb's Respite

実行時間制限: 3 秒 / メモリ制限: 1 GB

体力が整数 で表されるキャラクターがいる。キャラクターは正の整数で表される最大体力 を持つ。体力が変化し より大きくなった場合体力は となり、 より小さくなった場合は となってキャラクターは死亡する。

体力が変化する行動を 回行う。 回目の行動ではキャラクターの体力が だけ変化する。

キャラクターは魔法を使うことができる。魔法を使うと、魔法が持続している間、体力が 以下であるか、体力の変化により体力が 以下になる (死亡する場合を含む) 場合、体力が となり、魔法が切れるまで体力が変化しなくなる。

以下の 種類のクエリを 個処理せよ。

• クエリ : 整数 が与えられる。キャラクターの開始時の体力と最大体力が であり、 回目の行動の前から 回目の行動の後まで魔法を使ったとき、 回目の行動の後のキャラクターの体力を出力する。ただし、キャラクターが途中で死亡する場合、 を出力する。
• クエリ : 整数 が与えられる。 を に更新する。

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

• 
• 
• クエリ について、
• クエリ について、
• クエリ は つ以上存在する。

H 問題: Or Machine

実行時間制限: 4 秒 / メモリ制限: 1 GB

個の整数 が与えられる。

種類の操作がある。 番目の操作は以下のような操作である。

• 整数 が与えられる。 を と のビットごとの論理和に置き換える。

操作を の順に行い、操作 を行った後再び操作 に戻り繰り返す。合計で 回の操作を行ったとき、 の値を出力せよ。

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

• 
• 
• 
• 

I 問題: Organizing Colored Sheets

実行時間制限: 3 秒 / メモリ制限: 1 GB

のグリッドがあり、各マスは色で塗られているか塗られていないかのどちらかである。

を満たす整数 を選び、 の色紙のみを以下の条件を満たすようにグリッド上に何枚か配置したい。

• 色紙がグリッドの外部にはみ出ることはない。
• 色紙を回転してはならない。
• 各マスが 枚以上の色紙で覆われてもよい。
• 色で塗られていない各マスは 枚以上の色紙で覆われている。
• 色で塗られている各マスは色紙で覆われていない。

条件を満たすようにグリッド上に色紙を配置できるような整数 の組の個数を求めよ。

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

• 
• 色で塗られていないマスが つ以上存在する。

J 問題: Periodic Ruler

実行時間制限: 2 秒 / メモリ制限: 1 GB

無限に長い数直線の整数の位置にそれぞれ印が付いている。色は 以上 以下の整数で表され、 の位置の印の色は である。

付けられた印の色は周期 を持っている。ただし、周期とは、すべでの整数 に対し であるような最小の正の整数 である。

印の色について 個の情報が与えられる。 番目の情報は整数 と色 からなり、 の位置の印の色が であることを示す。

周期 としてありえない整数を列挙し、その個数とそれらの和を出力せよ。

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

• 
• 
• 
• ならば である。

K 問題: Three Competitions

実行時間制限: 5 秒 / メモリ制限: 1 GB

人の人が 回の大会に参加した。それぞれの大会で、 人の人はそれぞれ異なる順位を得た。

回中 回以上の大会で人 の順位が人 の順位より小さかったとき、人 が人 に勝ったという。また、人の列 であって、 に対して人 が人 に勝ち、また であるとき、人 は人 に間接的に勝ったという。

個のクエリが与えられる。各クエリでは、異なる人 が与えられるので、人 が人 に間接的に勝ったかどうか答えよ。

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

• 
• 
• 

L 問題: Utilitarianism 2

実行時間制限: 7 秒 / メモリ制限: 1 GB

人のワクチン生産者、 個の病院と 人の人がいる。人 は生産者 から病院 へ 個のワクチンを届けることができる。異なる人が同じ生産者と病院の組み合わせを持つことはない。また、それぞれのワクチン生産者と病院は 人の人しか利用してはならない。

それぞれの人に対し、その人がいない場合、 個の病院に届くワクチンの総数が何個減少するか求めよ。

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

• 
• 
• 
• 
• 
• ならば である。

M 問題: Yet Another Range Query Problem

実行時間制限: 3 秒 / メモリ制限: 1 GB

以上 以下の整数からなる長さ の数列 が与えられる。

の行列 がある。 のとき、 である。そうでないとき、 である。

個のクエリが与えられる。各クエリでは整数 が与えられるので、 を求めよ。

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

• 
• 
• 

問題文

A 問題: Automatic Sprayer 2

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

B 問題: Cilantro

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

C 問題: Equivalent Pipelines

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

D 問題: Flowerbed Redecoration

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

E 問題: Goose Coins

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

F 問題: Hedgehog Graph

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

G 問題: Lamb's Respite

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

H 問題: Or Machine

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

I 問題: Organizing Colored Sheets

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

J 問題: Periodic Ruler

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

K 問題: Three Competitions

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

L 問題: Utilitarianism 2

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

M 問題: Yet Another Range Query Problem

https://official.contest.yandex.ru/opencupXXII/contest/30766/problems/M/

AOJ 0367: Charging System for Network/ネットワークの課金システム

https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0367&lang=ja

解法

ネットワークはマシンを頂点としケーブルの太さを各辺の重みとする木と考えます。

add クエリが扱いにくいので、各頂点 に対し整数 を辺 の重みが常に となるようにすると、add クエリが に を加えるというクエリになります。 の初期値は BFS をすることで計算できます。

send クエリは、頂点 から頂点 の最短路を としたとき、 (ただし は が の倍数のとき 、そうでないとき ) を求めることに帰着され、これは列 ] の情報を の組として持つと、HLD にセグメント木を載せることで処理できます。

計算量は です。

実装

https://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=5956782

#include <bits/stdc++.h>
using namespace std;
struct monoid{
  bool e;
  long long L, R, S;
  monoid(): e(true){
  }
  monoid(long long x): e(false), L(x), R(x), S(0){
  }
};
monoid f(monoid A, monoid B, int K){
  if (A.e){
    return B;
  }
  if (B.e){
    return A;
  }
  monoid ans;
  ans.e = false;
  ans.L = A.L;
  ans.R = B.R;
  ans.S = A.S + B.S;
  if ((A.R + B.L) % K != 0){
    ans.S += A.R + B.L;
  }
  return ans;
};
struct segment_tree{
  int N;
  array<vector<monoid>, 2> ST;
  int K;
  segment_tree(){
  }
  segment_tree(vector<long long> &A, int K): K(K){
    int N2 = A.size();
    N = 1;
    while (N < N2){
      N *= 2;
    }
    ST[0] = vector<monoid>(N * 2 - 1);
    ST[1] = vector<monoid>(N * 2 - 1);
    for (int i = 0; i < N2; i++){
      ST[0][N - 1 + i] = monoid(A[i]);
      ST[1][N - 1 + i] = monoid(A[i]);
    }
    for (int i = N - 2; i >= 0; i--){
      ST[0][i] = f(ST[0][i * 2 + 1], ST[0][i * 2 + 2], K);
      ST[1][i] = f(ST[1][i * 2 + 2], ST[1][i * 2 + 1], K);
    }
  }
  void update(int i, int x){
    i += N - 1;
    ST[0][i].L += x;
    ST[0][i].R += x;
    ST[1][i].L += x;
    ST[1][i].R += x;
    while (i > 0){
      i = (i - 1) / 2;
      ST[0][i] = f(ST[0][i * 2 + 1], ST[0][i * 2 + 2], K);
      ST[1][i] = f(ST[1][i * 2 + 2], ST[1][i * 2 + 1], K);
    }
  }
  monoid range_fold(int L, int R, int d, int i, int l, int r){
    if (r <= L || R <= l){
      return monoid();
    } else if (L <= l && r <= R){
      return ST[d][i];
    } else {
      int m = (l + r) / 2;
      if (d == 0){
        return f(range_fold(L, R, d, i * 2 + 1, l, m), range_fold(L, R, d, i * 2 + 2, m, r), K);
      } else {
        return f(range_fold(L, R, d, i * 2 + 2, m, r), range_fold(L, R, d, i * 2 + 1, l, m), K);
      }
    }
  }
  monoid range_fold(int L, int R, int d){
    return range_fold(L, R, d, 0, 0, N);
  }
};
struct heavy_light_decomposition{
  vector<int> p, sz, in, next;
  segment_tree ST;
  int K;
  heavy_light_decomposition(vector<int> &p, vector<vector<int>> &c, vector<long long> &A, int K): p(p), K(K){
    int N = p.size();
    sz = vector<int>(N, 1);
    dfs1(c);
    in = vector<int>(N);
    next = vector<int>(N);
    next[0] = 0;
    int t = 0;
    dfs2(c, t);
    vector<long long> A2(N);
    for (int i = 0; i < N; i++){
      A2[in[i]] = A[i];
    }
    ST = segment_tree(A2, K);
  }
  void dfs1(vector<vector<int>> &c, int v = 0){
    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);
    }
  }
  void update(int v, int x){
    ST.update(in[v], x);
  }
  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]];
    }
  }
  monoid path_fold(int u, int v){
    int w = lca(u, v);
    monoid L;
    while (next[u] != next[w]){
      L = f(L, ST.range_fold(in[next[u]], in[u] + 1, 1), K);
      u = p[next[u]];
    }
    L = f(L, ST.range_fold(in[w], in[u] + 1, 1), K);
    monoid R;
    while (next[v] != next[w]){
      R = f(ST.range_fold(in[next[v]], in[v] + 1, 0), R, K);
      v = p[next[v]];
    }
    R = f(ST.range_fold(in[w] + 1, in[v] + 1, 0), R, K);
    return f(L, R, K);
  }
};
int main(){
  int N, K;
  cin >> N >> K;
  vector<vector<pair<int, int>>> E(N);
  for (int i = 0; i < N - 1; i++){
    int a, b, c;
    cin >> a >> b >> c;
    E[a].push_back(make_pair(c, b));
    E[b].push_back(make_pair(c, a));
  }
  vector<int> p(N, -1);
  vector<vector<int>> c(N);
  vector<long long> a(N);
  a[0] = 0;
  queue<int> q;
  q.push(0);
  while (!q.empty()){
    int v = q.front();
    q.pop();
    for (auto P : E[v]){
      int w = P.second;
      if (w != p[v]){
        p[w] = v;
        c[v].push_back(w);
        a[w] = P.first - a[v];
        q.push(w);
      }
    }
  }
  heavy_light_decomposition T(p, c, a, K);  
  int Q;
  cin >> Q;
  for (int i = 0; i < Q; i++){
    string S;
    cin >> S;
    if (S == "add"){
      int x, d;
      cin >> x >> d;
      T.update(x, d);
    }
    if (S == "send"){
      int s, t;
      cin >> s >> t;
      cout << T.path_fold(s, t).S << endl;
    }
  }
}

AOJ 2733: Cube Dividing

https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2733

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

問題概要

個の同じ大きさの立方体で構成された幅 、高さ 、奥行き の立方体がある。 を満たす各 について、左から 番目・下から 番目・前から 番目の立方体を取り除いた。残っている各立方体を頂点とし隣り合う立方体に対応する頂点の間に辺を張った無向グラフの連結成分の個数を求めよ。

解法

以下、 軸をそれぞれ左から右、下から上、前から後ろに取ります。

座標圧縮をして、見る必要のある 座標を絞ります。具体的には、 座標が 、、 の場所のみ考えればよいです。

各 座標について、その位置にある取り除いた立方体の 座標のリストを作り、同様に座標圧縮をします。さらに、各 座標について、その位置にある取り除いた立方体の 座標のリストを作り、ソートして取り除いた立方体の間の直方体に番号を振ります。これにより、立方体が取り除かれた後の立体は 個の直方体に分割されます。これらの直方体を頂点とし、接している つの直方体に対応する頂点の間に辺を張った無向グラフを作ることを考えます。

各 座標のそれぞれの隣接する つの 座標について、 座標が変化すると つの立方体がそれぞれどの直方体に属するか (あるいは、取り除かれていて立体に含まれていないか) がどのように変化するかを調べ、それらが同時に直方体に属している場合、その つの直方体は接しているので、辺を追加します。

次に、それぞれの隣接する つの 座標について、座標圧縮で得た考慮する必要のある 座標のリストの和集合を求めます。上と同様に、それぞれの 座標についての 座標の変化による立方体の所属の変化を調べ、辺を追加します。

グラフが完成したら、そのグラフを連結成分に分解し、連結成分の個数が答えとなります。

計算量は です。

実装

judge.u-aizu.ac.jp

#include <bits/stdc++.h>
using namespace std;
int main(){
  int A, B, C, N;
  cin >> A >> B >> C >> N;
  vector<int> X(N), Y(N), Z(N);
  for (int i = 0; i < N; i++){
    cin >> X[i] >> Y[i] >> Z[i];
  }
  vector<int> rx;
  rx.push_back(0);
  for (int i = 0; i < N; i++){
    rx.push_back(X[i]);
    if (X[i] < A - 1){
      rx.push_back(X[i] + 1);
    }
  }
  sort(rx.begin(), rx.end());
  rx.erase(unique(rx.begin(), rx.end()), rx.end());
  int A2 = rx.size();
  rx.push_back(A);
  for (int i = 0; i < N; i++){
    X[i] = lower_bound(rx.begin(), rx.end(), X[i]) - rx.begin();
  }
  vector<vector<int>> id(A2);
  for (int i = 0; i < N; i++){
    id[X[i]].push_back(i);
  }
  int V = 0;
  vector<pair<int, int>> E;
  vector<vector<int>> ry(A2);
  vector<int> B2(A2);
  vector<vector<vector<pair<int, int>>>> upd(A2);
  vector<vector<int>> uc(A2);
  for (int i = 0; i < A2; i++){
    ry[i].push_back(0);
    int cnt = id[i].size();
    for (int j = 0; j < cnt; j++){
      ry[i].push_back(Y[id[i][j]]);
      if (Y[id[i][j]] < B - 1){
        ry[i].push_back(Y[id[i][j]] + 1);
      }
    }
    sort(ry[i].begin(), ry[i].end());
    ry[i].erase(unique(ry[i].begin(), ry[i].end()), ry[i].end());
    B2[i] = ry[i].size();
    vector<vector<int>> id2(B2[i]);
    for (int j = 0; j < cnt; j++){
      int Y2 = lower_bound(ry[i].begin(), ry[i].end(), Y[id[i][j]]) - ry[i].begin();
      id2[Y2].push_back(id[i][j]);
    }
    upd[i].resize(B2[i]);
    for (int j = 0; j < B2[i]; j++){
      int cnt2 = id2[j].size();
      for (int k = 0; k < cnt2; k++){
        upd[i][j].push_back(make_pair(Z[id2[j][k]], -1));
      }
      vector<int> rz;
      rz.push_back(-1);
      rz.push_back(C);
      for (int k = 0; k < cnt2; k++){
        rz.push_back(Z[id2[j][k]]);
      }
      sort(rz.begin(), rz.end());
      int cnt3 = rz.size();
      for (int k = 0; k < cnt3 - 1; k++){
        if (rz[k + 1] - rz[k] > 1){
          upd[i][j].push_back(make_pair(rz[k] + 1, V));
          V++;
        }
      }
    }
    uc[i].resize(B2[i]);
    for (int j = 0; j < B2[i]; j++){
      uc[i][j] = upd[i][j].size();
    }
    for (int j = 0; j < B2[i] - 1; j++){
      vector<tuple<int, int, int>> upd2;
      for (int k = 0; k < 2; k++){
        for (int l = 0; l < uc[i][j + k]; l++){
          upd2.push_back(make_tuple(upd[i][j + k][l].first, k, upd[i][j + k][l].second));
        }
      }
      sort(upd2.begin(), upd2.end());
      int cnt2 = upd2.size();
      vector<int> c = {-1, -1};
      for (int k = 0; k < cnt2; k++){
        int t = get<0>(upd2[k]);
        int h = get<1>(upd2[k]);
        int v = get<2>(upd2[k]);
        c[h] = v;
        bool ok = true;
        if (k < cnt2 - 1){
          if (get<0>(upd2[k + 1]) == t){
            ok = false;
          }
        }
        if (ok){
          if (c[0] != -1 && c[1] != -1){
            E.push_back(make_pair(c[0], c[1]));
          }
        }
      }
    }
  }
  for (int i = 0; i < A2 - 1; i++){
    vector<int> ry2;
    for (int j = i; j <= i + 1; j++){
      for (int k = 0; k < B2[j]; k++){
        ry2.push_back(ry[j][k]);
      }
    }
    sort(ry2.begin(), ry2.end());
    ry2.erase(unique(ry2.begin(), ry2.end()), ry2.end());
    int cnt = ry2.size();
    for (int j = 0; j < cnt; j++){
      vector<int> yp(2);
      for (int k = 0; k < 2; k++){
        yp[k] = upper_bound(ry[i + k].begin(), ry[i + k].end(), ry2[j]) - ry[i + k].begin() - 1;
      }
      vector<tuple<int, int, int>> upd2;
      for (int k = 0; k < 2; k++){
        for (int l = 0; l < uc[i + k][yp[k]]; l++){
          upd2.push_back(make_tuple(upd[i + k][yp[k]][l].first, k, upd[i + k][yp[k]][l].second));
        }
      }
      sort(upd2.begin(), upd2.end());
      int cnt2 = upd2.size();
      vector<int> c = {-1, -1};
      for (int k = 0; k < cnt2; k++){
        int t = get<0>(upd2[k]);
        int h = get<1>(upd2[k]);
        int v = get<2>(upd2[k]);
        c[h] = v;
        bool ok = true;
        if (k < cnt2 - 1){
          if (get<0>(upd2[k + 1]) == t){
            ok = false;
          }
        }
        if (ok){
          if (c[0] != -1 && c[1] != -1){
            E.push_back(make_pair(c[0], c[1]));
          }
        }
      }
    }
  }
  int M = E.size();
  vector<vector<int>> E2(V);
  for (int i = 0; i < M; i++){
    int v = E[i].first;
    int w = E[i].second;
    E2[v].push_back(w);
    E2[w].push_back(v);
  }
  int ans = 0;
  vector<bool> used(V, false);
  for (int i = 0; i < V; i++){
    if (!used[i]){
      used[i] = true;
      ans++;
      queue<int> Q;
      Q.push(i);
      while (!Q.empty()){
        int v = Q.front();
        Q.pop();
        for (int w : E2[v]){
          if (!used[w]){
            used[w] = true;
            Q.push(w);
          }
        }
      }
    }
  }
  cout << ans << endl;
}

2021牛客暑期多校训练营5 (2021/07/31 12:00-17:00)

コンテストページ

ac.nowcoder.com

問題概要

A 問題: Away from College

(問題文を読んでいません　原文を読んでください)

B 問題: Boxes

実行時間制限: 1 秒 / メモリ制限: 262144 KB

個の箱があり、それぞれの箱には黒いボールまたは白いボールがそれぞれ の確率で入っている。箱は閉じられていて、中のボールを見ることはできない。

以下の操作 1 または操作 2 を繰り返すことにより、すべての箱に入っている玉の色を当てたい。

• 操作 1: 整数 を選ぶ。コスト を支払い、箱 を開けて入っているボールの色を知る。

• 操作 2: コスト を支払い、まだ開けられていない箱に入っている黒いボールの個数を教えてもらう。

すべての箱に入っている玉の色を当てるのに必要なコストの期待値の最小値を求めよ。

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

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

C 問題: Cheating and Stealing

実行時間制限: 2 秒 / メモリ制限: 262144 KB

W と L のみからなる長さ の文字列 が与えられる。 に対し、 を以下の操作で定義する。

1. 文字列 の接頭辞であって、接頭辞に含まれる W, L の個数をそれぞれ とおくと、 かつ が成立するもののうち最も短いものを取る。
2. 条件を満たす接頭辞が存在しない場合、操作を終了する。得た得点が の値である。
3. 条件を満たす接頭辞が存在する場合、その接頭辞に含まれる W の個数が L の個数より多いならば 1 点の得点を得る。その後、その接頭辞を削除し、1. に戻る。

を で割った余りを求めよ。

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

• 

D 問題: Double Strings

実行時間制限: 2 秒 / メモリ制限: 262144 KB

文字列 が与えられる。 の部分列 と の部分列 の組であって、 を満たすものの個数を で割った余りを求めよ。ただし、同じ部分文字列であっても や の異なる位置から取ったものは区別する。

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

• 
• は小文字のアルファベットからなる。

E 問題: Eert Esiwtib

実行時間制限: 3 秒 / メモリ制限: 262144 KB

長さ の数列 と頂点 を根とする 頂点の木が与えられる。木の各辺には OR, AND, XOR のうち 1 つの演算子が書かれている。また、木の頂点 には整数 が書かれている。

を木の異なる 2 頂点とし、それらの間のパスの頂点を とおく。また、頂点 を結ぶ辺に書かれている演算子を とおく。このとき、このパスの重みを と定義する。

個のクエリが与えられる。各クエリでは、整数 と木の頂点 が与えられる。ただし、 は葉ではないことが保証される。頂点 に書かれた整数が に変化したとき、 が の先祖であるような頂点 すべて (ただし頂点 自身は除く) について、 パスの重みを求め、それらの OR, AND, XOR をそれぞれ求めよ。

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

• 
• 
• 
• 

F 問題: Finding Points

実行時間制限: 1 秒 / メモリ制限: 262144 KB

凸多角形 が与えられる。ただし、点 は反時計回りに並んでいる。 の座標は である。この多角形の内部の点 に対する の最小値としてありうる値の最大値を求めよ。

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

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

• 
• 

G 問題: Greater Integer, Better LCM

実行時間制限: 2 秒 / メモリ制限: 262144 KB

正の整数 が与えられる。ただし は素因数分解した形で与えられ、 である。非負整数 であって を満たすものに対する の最小値を求めよ。

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

• 
• 
• は素数
• 
• 

H 問題: Holding Two

実行時間制限: 1 秒 / メモリ制限: 262144 KB

正の整数 が与えられる。以下の条件を満たす各要素が 0 または 1 である の行列を構築せよ。条件を満たす行列が存在しない場合、-1 と出力せよ。

• 行列の異なる つの要素 であって、 を満たすものが存在しない。

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

• 

I 問題: Interval Queries

実行時間制限: 4 秒 / メモリ制限: 262144 KB

長さ の数列 が与えられる。

集合 に対し、 を がすべて の要素であるような が存在する最大の の値とする。

個のクエリが与えられる。各クエリでは、整数 が与えられるので、 を で割った余りを求めよ。

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

• 
• 
• 
• 
• 

J 問題: Jewels

実行時間制限: 1 秒 / メモリ制限: 262144 KB

個の宝石があり、宝石 は時刻 秒において にある。 秒につき 個の宝石を原点とその宝石の距離の二乗のコストで得ることができる。 個の宝石をすべて得るのに必要なコストの最小値を求めよ。

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

• 
• 
• 

K 問題: King of Range

実行時間制限: 1 秒 / メモリ制限: 262144 KB

長さ の数列 が与えられる。

個のクエリが与えられる。各クエリでは整数 が与えられるので、 なる の組であって、 を満たすものの個数を求めよ。

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

• 
• 
• 
• 

問題文

A 問題: Away from College

https://ac.nowcoder.com/acm/contest/11256/A

B 問題: Boxes

https://ac.nowcoder.com/acm/contest/11256/B

C 問題: Cheating and Stealing

https://ac.nowcoder.com/acm/contest/11256/C

D 問題: Double Strings

https://ac.nowcoder.com/acm/contest/11256/D

E 問題: Eert Esiwtib

https://ac.nowcoder.com/acm/contest/11256/E

F 問題: Finding Points

https://ac.nowcoder.com/acm/contest/11256/F

G 問題: Greater Integer, Better LCM

https://ac.nowcoder.com/acm/contest/11256/G

H 問題: Holding Two

https://ac.nowcoder.com/acm/contest/11256/H

I 問題: Interval Queries

https://ac.nowcoder.com/acm/contest/11256/I

J 問題: Jewels

https://ac.nowcoder.com/acm/contest/11256/J

K 問題: King of Range

https://ac.nowcoder.com/acm/contest/11256/K

2021牛客暑期多校训练营4 (2021/07/26 12:00-17:00)

コンテストページ

ac.nowcoder.com

問題概要

A 問題: Course

実行時間制限: 3 秒 / メモリ制限: 262144 KB

頂点の根付き木と長さ の数列 と が与えられる。 個のクエリに答えよ。

番目のクエリでは整数 が与えられるので、長さ の非負整数の列 で、以下の条件を満たすものの個数を で割った余りを求めよ。

• について、以下が成り立つ。
  • を頂点 の部分木の頂点の番号の集合とすると、
• 

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

• 
• 
• 
• 
• 

B 問題: Sample Game

実行時間制限: 1 秒 / メモリ制限: 262144 KB

以上 以下の整数を、 は確率 で生成する乱数生成器がある。

以下の操作を行う。

1. 乱数生成器で整数を つ生成する。生成した整数を とおく。
2. が今までに生成したすべての整数と比べ等しいまたは大きい場合、1. に戻る。そうでない場合、3. に進む。
3. 生成した整数の個数を として、 の得点を得る。

得点の期待値を既約分数で表し、 で出力せよ。ただし、得点の期待値は有理数であることが証明できる。

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

• 
• 

C 問題: LCS

実行時間制限: 1 秒 / メモリ制限: 262144 KB

つの文字列 に対し、 を の最長共通部分列の長さとする。

整数 が与えられる。小文字のアルファベットからなる 文字の文字列 であって、 となるものを一つ構築するか、条件を満たす文字列が存在しないと報告せよ。

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

• 
• 

D 問題: Rebuild Tree

実行時間制限: 1 秒 / メモリ制限: 262144 KB

頂点の木が与えられる。木の辺の集合を とする。また、 頂点の完全グラフの辺の集合を とする。

整数 が与えられる。以下の条件をすべて満たす集合 の組の個数を で割った余りを求めよ。

• 
• 
• 
• 
• 辺の集合が である 頂点のグラフは木である。

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

• 
• 

E 問題: Tree Xor

実行時間制限: 2 秒 / メモリ制限: 262144 KB

をビット単位の排他的論理和とする。

頂点の木が与えられる。木の各辺には整数 が書いてある。また、長さ の数列 と が与えられる。長さ の非負整数の列 であって、以下の条件をすべて満たすものの個数を求めよ。

• 
• 木の各辺 に対し、 である。

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

• 
• 
• 

F 問題: Just a joke

実行時間制限: 1 秒 / メモリ制限: 262144 KB

頂点 辺のグラフ が与えられる。Alice と Bob が以下の操作のうち 1 つを繰り返すゲームをする。操作ができなくなった人が負けである。勝者は誰か求めよ。

• の辺を 1 本選び、それを削除する。
• の連結成分で閉路を含まないものを 1 つ選び、削除する。

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

• 
• 

G 問題: Product

実行時間制限: 1 秒 / メモリ制限: 262144 KB

である長さ の非負整数の列 すべてに対する の総和を で求めよ。

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

• 
• 
• 

H 問題: Convolution

実行時間制限: 3 秒 / メモリ制限: 262144 KB

をビット単位の排他的論理和とする。

を 番目の素数とする。 と が と素因数分解されるとき、 と定義する。

長さ の整数の列 と整数 が与えられる。 としたとき、 を求めよ。

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

• 
• 
• 

I 問題: Inverse Pair

実行時間制限: 1 秒 / メモリ制限: 262144 KB

長さ の数列 の重みを、 となる の個数とする。

長さ の順列 が与えられる。 を満たす長さ の数列 を選び、 としたときの の重みの最小値を求めよ。

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

• 

J 問題: Average

実行時間制限: 1 秒 / メモリ制限: 262144 KB

要素の数列 と 要素の数列 が与えられる。

の行列 がある。 は を満たす。

のうち 個以上の連続する行と 個以上の連続する列を選ぶ。選ばれた行・列の部分行列の平均値の最大値を求めよ。

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

• 
• 
• 
• 
• 

問題文

A 問題: Course

https://ac.nowcoder.com/acm/contest/11255/A

B 問題: Sample Game

https://ac.nowcoder.com/acm/contest/11255/B

C 問題: LCS

https://ac.nowcoder.com/acm/contest/11255/C

D 問題: Rebuild Tree

https://ac.nowcoder.com/acm/contest/11255/D

E 問題: Tree Xor

https://ac.nowcoder.com/acm/contest/11255/E

F 問題: Just a joke

https://ac.nowcoder.com/acm/contest/11255/F

G 問題: Product

https://ac.nowcoder.com/acm/contest/11255/G

H 問題: Convolution

https://ac.nowcoder.com/acm/contest/11255/H

I 問題: Inverse Pair

https://ac.nowcoder.com/acm/contest/11255/I

J 問題: Average

https://ac.nowcoder.com/acm/contest/11255/J

AOJ 1198: Don't Cross the Circles!/円を横切るな！

https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1198&lang=ja

解法

のうち一方のみが含まれる円が 1 つ以上存在する場合、 と をその円と交差しないように結ぶことはできないので、答えは明らかに NO となります。

がともに 1 個以上の円に含まれていて、 を含む円の集合と を含む円の集合が一致する場合、3 つ以上の円に共通部分はなく 2 つの円が接することはないという条件から、答えは必ず YES となります。

よって、 がともにどの円にも含まれていない場合のみ考えればよいです。

個の円の中心を考え、円 が二点で交わるとき、またそのときのみに、円 の中心とと円 の中心を線分で結ぶと、2 つの線分は端点以外では共有点を持たず、点 をどの円とも交差しないように結べることとどの線分とも交差しないように結べることは同値になります。

個の円の中心を頂点、中心を結ぶ線分を辺とした平面グラフ を考えると、 の辺は平面を何個かの領域に分割し、点 をどの辺とも交差しないように結べることは点 が同じ領域に属することと同値になります。 が木である場合は領域が 1 つしかないので答えは必ず YES になります。そうでない場合は、 には閉路が必ず存在します。閉路に現れる頂点を順に列挙し、それぞれの頂点に対応する円の中心を順に線分で結んだ多角形を考えます。もし点 のうち一方のみがこの多角形に含まれている場合、多角形の辺と交差せずに点 を結ぶことはできないので、答えは NO となります。そうでない場合、閉路の辺を一つ取りその辺を取り除き とすると、辺が平面を分割している領域のうちその辺を境に隣接している二つ ( とします) が併合され新しい領域ができます。ここで、点 がそれぞれ領域 または に属していることはありえないので、点 が同じ領域に属することは、グラフ の辺が平面を分割する領域について点 が同じ領域に属することと同値になります。よって、点 のうち一方のみが多角形の内部にあることで答えが NO であることが確定するかグラフ が木になり答えが YES が確定するまで から閉路を取り辺を取り除くことを繰り返すことで、点 をどの円とも交差しないように結べるかどうか判定することができます。

時間計算量は です。

実装

judge.u-aizu.ac.jp

#include <bits/stdc++.h>
using namespace std;
const double EPS = 0.0001;
struct point{
  double x, y;
  point(){
  }
  point(double x, double y): x(x), y(y){
  }
  point operator -(point P){
    return point(x - P.x, y - P.y);
  }
};
double abs(point P){
  return sqrt(P.x * P.x + P.y * P.y);
}
double dist(point P, point Q){
  return abs(Q - P);
}
double cross(point P, point Q){
  return P.x * Q.y - P.y * Q.x;
}
struct line{
  point A, B;
  line(point A, point B): A(A), B(B){
  }
};
point vec(line L){
  return L.B - L.A;
}
bool segment_intersect(line L1, line L2){
  if (cross(L1.A - L2.A, vec(L2)) * cross(L1.B - L2.A, vec(L2)) > 0){
    return false;
  }
  if (cross(L2.A - L1.A, vec(L1)) * cross(L2.B - L1.A, vec(L1)) > 0){
    return false;
  }
  return true;
}
bool point_in_polygon(point P, vector<point> Q){
  int N = Q.size();
  point P2 = point(P.x + 100000, P.y + 123456);
  int cnt = 0;
  for (int i = 0; i < N; i++){
    line L1(Q[i], Q[(i + 1) % N]);
    line L2(P, P2);
    if (segment_intersect(L1, L2)){
      cnt++;
    }
  }
  if (cnt % 2 == 1){
    return true;
  } else {
    return false;
  }
}
struct circle{
  point C;
  double r;
  circle(){
  }
};
bool point_in_circle(point P, circle C){
  return dist(P, C.C) < C.r;
}
bool circle_intersects(circle C1, circle C2){
  double d = dist(C1.C, C2.C);
  return abs(C1.r - C2.r) - EPS < d && d < C1.r + C2.r + EPS;
}
void dfs(vector<vector<int>> &E, vector<int> &r, vector<int> &p, vector<int> &d, int r2, int v){
  r[v] = r2;
  for (int w : E[v]){
    if (r[w] == -1){
      d[w] = d[v] + 1;
      p[w] = v;
      dfs(E, r, p, d, r2, w);
    }
  }
}
vector<int> detect_cycle(vector<vector<int>> E){
  int N = E.size();
  vector<int> r(N, -1);
  vector<int> p(N, -1);
  vector<int> d(N, 0);
  for (int i = 0; i < N; i++){
    if (p[i] == -1){
      dfs(E, r, p, d, i, i);
    }
  }
  for (int i = 0; i < N; i++){
    for (int j : E[i]){
      if (r[i] == r[j] && d[j] - d[i] > 1){
        vector<int> c;
        for (int v = j; v != i; v = p[v]){
          c.push_back(v);
        }
        c.push_back(i);
        return c;
      }
    }
  }
  return vector<int>();
}
int main(){
  while (true){
    int n, m;
    cin >> n >> m;
    if (n == 0 && m == 0){
      break;
    }
    vector<circle> C(n);
    for (int i = 0; i < n; i++){
      cin >> C[i].C.x >> C[i].C.y >> C[i].r;
    }
    for (int i = 0; i < m; i++){
      point P, Q;
      cin >> P.x >> P.y >> Q.x >> Q.y;
      set<int> st1, st2;
      for (int j = 0; j < n; j++){
        if (point_in_circle(P, C[j])){
          st1.insert(j);
        }
        if (point_in_circle(Q, C[j])){
          st2.insert(j);
        }
      }
      if (!st1.empty() || !st2.empty()){
        if (st1 == st2){
          cout << "YES";
        } else {
          cout << "NO";
        }
      } else {
        vector<vector<int>> E(n);
        for (int j = 0; j < n; j++){
          for (int k = j + 1; k < n; k++){
            if (circle_intersects(C[j], C[k])){
              E[j].push_back(k);
              E[k].push_back(j);
            }
          }
        }
        bool ok = true;
        while (true){
          vector<int> c = detect_cycle(E);
          if (c.empty()){
            break;
          }
          int cnt = c.size();
          vector<point> p(cnt);
          for (int j = 0; j < cnt; j++){
            p[j] = C[c[j]].C;
          }
          if (point_in_polygon(P, p) != point_in_polygon(Q, p)){
            ok = false;
          }
          for (int j = 0; j < E[c[0]].size(); j++){
            if (E[c[0]][j] == c[1]){
              E[c[0]].erase(E[c[0]].begin() + j);
              break;
            }
          }
          for (int j = 0; j < E[c[1]].size(); j++){
            if (E[c[1]][j] == c[0]){
              E[c[1]].erase(E[c[1]].begin() + j);
              break;
            }
          }
        }
        if (ok){
          cout << "YES";
        } else {
          cout << "NO";
        }
      }
      if (i < m - 1){
        cout << ' ';
      }
    }
    cout << endl;
  }
}

APIO2021 参加記

APIO2021 に参加しました。

競技

Hexagonal Territory を読む。六角グリッドでやばそう。とりあえず Territory (難易度 11) を思い出すがよくわからない。9 点の部分点は数学で簡単に取れそうなので取る。Rainforest Jumps を読む。4 点が自明なので取る。8 点もワーシャルフロイド法をするだけなので、取る。Road Closures を読む。5 点が自明なので取る。7 点も簡単な DP なので取る。

簡単そうな Rainforest Jumps に戻る。小課題 3 の 13 点は距離の配列が得られるので長方形領域の最小値を求めることに帰着。簡単な解法が思いつかなかったのでセグ木を書く。セグ木を 2000 本持たせる を投げる。log が付いているので若干不安だが、通った。

小課題 4 を見る。 なのでそれぞれの樹から飛び移れる樹を stack を使い で取得し、BFS でクエリに答える。コードを投げるが、なかなかジャッジされない。ジャッジキューが詰まっているとの連絡が来ているので、とりあえず別の問題に移る。

Hexagonal Territory の小課題 3 は BFS で解けるとわかっていて実装を後回しにしていたので、実装をして投げる。提出欄を見ると、なんと今までに投げたすべての提出が WJ 状態に戻っていて、リジャッジが行われているとの連絡が来る。このあたりで開始から 1 時間経過。

Rainforest Jumps に戻り、小課題 5 を解く。貪欲に高いほうの樹に飛び移る戦略がだいたい正当なので、ダブリングを実装して投げる。Rainforest Jumps の小課題 3・4 はどうせ次数を持つ木 DP なので、適当に を実装し投げる。なかなかジャッジが返ってこないので clar を投げる。ジャッジ詰まりの影響でコンテスト時間が 30 分延長になるとの連絡が入る。

残りの問題を考察するが、よくわからない。コンテスト開始から 2 時間経過。ジャッジ詰まりのため各問題に 5 分に一回の提出制限がかけられるとの連絡があり、不安になる。

しばらくして、ジャッジが返り始めるので眺めると、投げた提出が何個か落ちているので確認。Rainforest Jumps の小課題 5 が落ちているので適当に修正し投げる。Hexagonal Territory の愚直 BFS も落ちたので確認すると点数の計算方法を誤っていたので、計算を修正すると通る。Road Closures の木 DP も落ちているので確認すると誤解をしているので直す。コンテストがさらに 30 分延長されて 6 時間になり、提出制限が元に戻る。

Hexagonal Territory と Road Closures は通ったが、Rainforest Jumps が通らないので、ワーシャルフロイド法の結果と比較するランダムチェッカーを書くと、貪欲をすると超えてしまう状態の後に二回以上移動する必要があることがあることを見落としていたことに気付き、右方向への移動だけでのダブリングを別に持ち、いろいろデバッグをすると通る。小課題 6 は二分探索で簡単に小課題 5 に帰着するので、実装。満点も取れそうなのでいろいろ考察し、何回か WA を出しながらなんとか通す。コンテスト開始から約 4 時間が経った。

Hexagonal Territory は自明な小課題以外の得点を取れていないので、面積を求めればよい。ピックの定理のようなものが使えるのではないかと気付き、実装をする。Road Closures の小課題 5 も考察する。マージテクをしたり、木の次数 の頂点の個数が 個であることの利用を考えるが、解法にはたどり着けず終わった。結果は 47+100+38=183。木はどちらかというと得意な分野なのにあまり点数が取れなくて少し悔しい。

終了後

人々の得点を見る。KoD さんと blackyuki さんが Road Closures で満点を取り 200↑ の得点を得ていた。すごい。

結果が発表される。得点は日本 3 位で銀メダルらしい。