UTPC 2020 - SSRS の競プロ日記

UTPC 2020 - AtCoder

UTPC 2020 に Nachia さんとチームを組んで参加しました。

A 問題

序盤は A 問題は任せて B 以降の問題文をすべて読むと決めたので、読みませんでした。Nachia さんが通してくれました。

H 問題

何人かが通しているので、少し考えるとうまくシミュレーションすれば自明であることがわかります。答えが $H+W$ のときは $H+W-1$ にしなければならないので 1 ペナ。

#include <bits/stdc++.h>
using namespace std;
int main(){
  int H, W;
  cin >> H >> W;
  vector<string> S(H);
  for (int i = 0; i < H; i++){
    cin >> S[i];
  }
  vector<bool> row_used(H, false);
  vector<bool> col_used(W, false);
  vector<int> row_b(H, 0), row_w(H, 0), col_b(W, 0), col_w(W, 0);
  for (int i = 0; i < H; i++){
    for (int j = 0; j < W; j++){
      if (S[i][j] == '#'){
        row_b[i]++;
        col_b[j]++;
      }
      if (S[i][j] == '.'){
        row_w[i]++;
        col_w[j]++;
      }
    }
  }
  queue<int> Q;
  for (int i = 0; i < H; i++){
    if (row_b[i] == 0 || row_w[i] == 0){
      row_used[i] = true;
      Q.push(i);
    }
  }
  for (int i = 0; i < W; i++){
    if (col_b[i] == 0 || col_w[i] == 0){
      col_used[i] = true;
      Q.push(H + i);
    }
  }
  int ans = 0;
  while (!Q.empty()){
    int v = Q.front();
    Q.pop();
    ans++;
    if (v < H){
      for (int i = 0; i < W; i++){
        if (!col_used[i]){
          if (S[v][i] == '#'){
            col_b[i]--;
          }
          if (S[v][i] == '.'){
            col_w[i]--;
          }
          if (col_b[i] == 0 || col_w[i] == 0){
            col_used[i] = true;
            Q.push(H + i);
          }
        }
      }
    }
    if (v >= H){
      v -= H;
      for (int i = 0; i < H; i++){
        if (!row_used[i]){
          if (S[i][v] == '#'){
            row_b[i]--;
          }
          if (S[i][v] == '.'){
            row_w[i]--;
          }
          if (row_b[i] == 0 || row_w[i] == 0){
            row_used[i] = true;
            Q.push(i);
          }
        }
      }
    }
  }
  if (ans == H + W){
    ans = H + W - 1;
  }
  cout << ans << endl;
}

D 問題

$M$ をソートして考えると、選ぶアイドルのうち $M$ が最も小さい人が持っている衣装は残り全員が持っているので、この性質を利用したいです。使う衣装は衣装 $1$ であるとしても問題なさそうなので、よく考えると、DP で部分点を取ることができました。

atcoder.jp

#include <bits/stdc++.h>
using namespace std;
const long long MOD = 998244353;
long long modpow(long long a, long long b){
    long long ans = 1;
    while (b > 0){
        if (b % 2 == 1){
            ans *= a;
            ans %= MOD;
        }
        a *= a;
        a %= MOD;
        b /= 2;
    }
    return ans;
}
long long modinv(long long a){
    return modpow(a, MOD - 2);
}
vector<long long> mf = {1};
vector<long long> mfi = {1};
long long modfact(int n){
    if (mf.size() > n){
        return mf[n];
    } else {
        for (int i = mf.size(); i <= n; i++){
            long long next = mf.back() * i % MOD;
            mf.push_back(next);
            mfi.push_back(modinv(next));
        }
        return mf[n];
    }
}
long long modfactinv(int n){
    if (mfi.size() > n){
        return mfi[n];
    } else {
        return modinv(modfact(n));
    }
}
long long modbinom(int n, int k){
    if (n < 0 || k < 0 || k > n){
        return 0;
    } else {
        return modfact(n) * modfactinv(k) % MOD * modfactinv(n - k) % MOD;
    }
}
int main(){
  int N, K;
  cin >> N >> K;
  assert(N <= 2000);
  vector<int> M(N);
  for (int i = 0; i < N; i++){
    cin >> M[i];
  }
  sort(M.begin(), M.end());
  vector<long long> M2(N);
  for (int i = 0; i < N; i++){
    M2[i] = modinv(M[i]);
  }
  vector<vector<long long>> dp(N + 1, vector<long long>(K, 0));
  dp[N][0] = 1;
  for (int i = N - 1; i >= 0; i--){
    for (int j = 0; j < K; j++){
      dp[i][j] += dp[i + 1][j];
      dp[i][j] %= MOD;
      if (j < K - 1){
        dp[i][j + 1] += dp[i + 1][j] * M2[i] % MOD;
        dp[i][j + 1] %= MOD;
      }
    }
  }
  long long ans = 0;
  for (int i = 0; i < N; i++){
    ans += dp[i + 1][K - 1];
  }
  ans %= MOD;
  ans *= modinv(modbinom(N, K));
  ans %= MOD;
  cout << ans << endl;
}

続いて満点解法を考えます。逆から見ると面倒なので $M$ は降順にソートすることにすると、 $\displaystyle{f _ i(x) = 1 + \frac{x}{M _ i}}$ としたときの $\displaystyle{\binom{N}{K} [x ^ {K-1} ] (1 + f _ 1 + f _ 1f _ 2 + \cdots + f _ 1f _ 2 \cdots f _ N)}$ が答えになることがわかり、これは中央で分割して全体の積と合わせて計算するのを再帰的に行うと計算量 $O(N \log ^ 2 N)$ で計算できました。

atcoder.jp

#include <bits/stdc++.h>
#include <atcoder/convolution>
using namespace std;
using namespace atcoder;
const long long MOD = 998244353;
long long modpow(long long a, long long b){
    long long ans = 1;
    while (b > 0){
        if (b % 2 == 1){
            ans *= a;
            ans %= MOD;
        }
        a *= a;
        a %= MOD;
        b /= 2;
    }
    return ans;
}
long long modinv(long long a){
    return modpow(a, MOD - 2);
}
vector<long long> mf = {1};
vector<long long> mfi = {1};
long long modfact(int n){
    if (mf.size() > n){
        return mf[n];
    } else {
        for (int i = mf.size(); i <= n; i++){
            long long next = mf.back() * i % MOD;
            mf.push_back(next);
            mfi.push_back(modinv(next));
        }
        return mf[n];
    }
}
long long modfactinv(int n){
    if (mfi.size() > n){
        return mfi[n];
    } else {
        return modinv(modfact(n));
    }
}
long long modbinom(int n, int k){
    if (n < 0 || k < 0 || k > n){
        return 0;
    } else {
        return modfact(n) * modfactinv(k) % MOD * modfactinv(n - k) % MOD;
    }
}
pair<vector<long long>, vector<long long>> dfs(vector<int> &M, int l, int r){
  if (l == r){
    vector<long long> f = {0};
    return make_pair(f, f);
  } else if (r - l == 1){
    vector<long long> f = {1, modinv(M[l])};
    return make_pair(f, f);
  } else {
    int m = (l + r) / 2;
    pair<vector<long long>, vector<long long>> P = dfs(M, l, m);
    pair<vector<long long>, vector<long long>> Q = dfs(M, m, r);
    vector<long long> f = convolution(P.second, Q.first);
    int sz = P.first.size();
    for (int i = 0; i < sz; i++){
      f[i] += P.first[i];
      f[i] %= MOD;
    }
    vector<long long> g = convolution(P.second, Q.second);
    return make_pair(f, g);
  }
}
int main(){
  int N, K;
  cin >> N >> K;
  vector<int> M(N);
  for (int i = 0; i < N; i++){
    cin >> M[i];
  }
  sort(M.begin(), M.end(), greater<int>());
  long long ans = dfs(M, 0, N - 1).first[K - 1];
  if (K == 1){
    ans++;
  }
  ans *= modinv(modbinom(N, K));
  ans %= MOD;
  cout << ans << endl;
}

G 問題

制約から、 $B$ は $A$ に行や列を交換したり $-1$ 倍したりする操作を適用して生成するのではないかと考えましたが、なかなか解けず、二人で議論をすると、 $M = 2 ^ {N-1}$ で構築する方法が生えました。

atcoder.jp

#include <bits/stdc++.h>
using namespace std;
int main(){
  int N;
  cin >> N;
  vector<vector<int>> A(N, vector<int>(N));
  for (int i = 0; i < N; i++){
    for (int j = 0; j < N; j++){
      cin >> A[i][j];
    }
  }
  cout << (1 << (N - 1)) << endl;
  for (int i = 0; i < (1 << (N - 1)); i++){
    vector<vector<int>> B = A;
    for (int j = 0; j < N - 1; j++){
      if ((i >> j & 1) == 1){
        for (int k = 0; k < N; k++){
          if (k != j){
            B[j][k] *= -1;
            B[k][j] *= -1;
          }
        }
      }
    }
    for (int j = 0; j < N; j++){
      for (int k = 0; k < N; k++){
        cout << B[j][k];
        if (k < N - 1){
          cout << ' ';
        }
      }
      cout << endl;
    }
  }
}

J 問題

適当に貪欲法でやって WA が出たので、Nachia さんに投げました。

I 問題

グラフ上のクエリで難しそうに見えたので考察していませんでしたが、木上のクエリに帰着してくれたので考えました。以下のようなクエリです。

$N$ 頂点の木と $M-(N-1)$ 個の 2 頂点の組が与えられます。木のある辺を削除し、そのとき初めて非連結になった頂点の組の番号を列挙してください。

木がどんどん分割されていくので、マージテクの逆を疑いますが、頂点の個数と頂点対の個数のどちらの大きさで分割するかが定まらなかったので、別の方針を考えたところ、以下のような方針を思いつきました。

木を HL 分解し、辺に番号を振る。また、2 頂点の組に対しそれらの間のパスで使用する辺の番号は $O(\log N)$ 個の区間の和集合になるので、それらの区間を列挙する。
クエリで木のある辺が与えられたとき、非連結になる頂点の組の番号を列挙することは、その辺の番号を含む区間を列挙しそれらを削除することに帰着する。
これは JOI の Port Facility や Treatment Project で既出。区間の左端でソートし、区間の右端を区間 max のセグメント木に載せればよい。

以上を実装すればよいです。実装は重めで、AC を得るまで約 1 時間かかりました。

atcoder.jp

#include <bits/stdc++.h>
using namespace std;
struct unionfind{
  vector<int> p;
  unionfind(int N): p(N, -1){    
  }
  int root(int x){
    if (p[x] < 0){
      return x;
    } else {
      p[x] = root(p[x]);
      return p[x];
    }
  }
  bool same(int x, int y){
    return root(x) == root(y);
  }
  void unite(int x, int y){
    x = root(x);
    y = root(y);
    if (p[x] < p[y]){
      swap(x, y);
    }
    p[y] += p[x];
    p[x] = y;
  }
};
struct heavy_light_decomposition{
  vector<int> p, sz, in, next, id;
  heavy_light_decomposition(vector<int> &p, vector<vector<int>> &c): p(p){
    int N = p.size();
    sz = vector<int>(N, 1);
    dfs1(c);
    in = vector<int>(N);
    next = vector<int>(N, 0);
    int t = 0;
    dfs2(c, t);
  }
  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);
    }
  }
  int operator [](int v){
    return in[v];
  }
  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]];
    }
  }
  vector<pair<int, int>> path_ranges(int u, int v){
    int w = lca(u, v);
    vector<pair<int, int>> ans;
    while (next[u] != next[w]){
      ans.push_back(make_pair(in[next[u]], in[u] + 1));
      u = p[next[u]];
    }
    ans.push_back(make_pair(in[w] + 1, in[u] + 1));
    while (next[v] != next[w]){
      ans.push_back(make_pair(in[next[v]], in[v] + 1));
      v = p[next[v]];
    }
    ans.push_back(make_pair(in[w] + 1, in[v] + 1));
    return ans;
  }
};
struct segment_tree{
  int N;
  vector<pair<int, int>> ST;
  segment_tree(vector<int> &A){
    int n = A.size();
    N = 1;
    while (N < n){
      N *= 2;
    }
    ST = vector<pair<int, int>>(N * 2 - 1, make_pair(-1, -1));
    for (int i = 0; i < n; i++){
      ST[N - 1 + i] = make_pair(A[i], i);
    }
    for (int i = N - 2; i >= 0; i--){
      ST[i] = max(ST[i * 2 + 1], ST[i * 2 + 2]);
    }
  }
  void update(int k){
    k += N - 1;
    ST[k] = make_pair(-1, -1);
    while (k > 0){
      k = (k - 1) / 2;
      ST[k] = max(ST[k * 2 + 1], ST[k * 2 + 2]);
    }
  }
  pair<int, int> range_max(int L, int R, int i, int l, int r){
    if (r <= L || R <= l){
      return make_pair(-1, -1);
    } else if (L <= l && r <= R){
      return ST[i];
    } else {
      int m = (l + r) / 2;
      return max(range_max(L, R, i * 2 + 1, l, m), range_max(L, R, i * 2 + 2, m, r));
    }
  }
  pair<int, int> range_max(int L, int R){
    return range_max(L, R, 0, 0, N);
  }
};
int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int N, M;
  cin >> N >> M;
  vector<int> A(M), B(M), C(M);
  for (int i = 0; i < M; i++){
    cin >> A[i] >> B[i] >> C[i];
    A[i]--;
    B[i]--;
  }
  vector<tuple<int, int, int, int>> E(M);
  for (int i = 0; i < M; i++){
    E[i] = make_tuple(C[i], A[i], B[i], i);
  }
  sort(E.begin(), E.end());
  vector<bool> tree(M);
  vector<vector<pair<int, int>>> E2(N);
  unionfind UF(N);
  for (int i = 0; i < M; i++){
    int a = get<1>(E[i]);
    int b = get<2>(E[i]);
    int id = get<3>(E[i]);
    if (UF.same(a, b)){
      tree[id] = false;
    } else {
      UF.unite(a, b);
      tree[id] = true;
      E2[a].push_back(make_pair(b, id));
      E2[b].push_back(make_pair(a, id));
    }
  }
  vector<int> p(N, -1);
  vector<int> p_id(N, -1);
  vector<vector<int>> c(N);
  queue<int> q;
  q.push(0);
  while (!q.empty()){
    int v = q.front();
    q.pop();
    for (auto P : E2[v]){
      int w = P.first;
      if (w != p[v]){
        p[w] = v;
        p_id[w] = P.second;
        c[v].push_back(w);
        q.push(w);
      }
    }
  }
  heavy_light_decomposition HLD(p, c);
  vector<tuple<int, int, int>> path;
  for (int i = 0; i < M; i++){
    if (!tree[i]){
      vector<pair<int, int>> tmp = HLD.path_ranges(A[i], B[i]);
      for (auto P : tmp){
        path.push_back(make_tuple(P.first, P.second, i));
      }
    }
  }
  sort(path.begin(), path.end());
  int range_cnt = path.size();
  vector<int> cnt(N + 1, 0);
  for (int i = 0; i < range_cnt; i++){
    int l = get<0>(path[i]);
    cnt[l]++;
  }
  vector<int> start(N + 1);
  start[0] = 0;
  for (int i = 0; i < N; i++){
    start[i + 1] = start[i] + cnt[i] + 1;
  }
  vector<tuple<int, int, int>> range(range_cnt);
  vector<int> ccnt(N + 1, -1);
  int id_max = 0;
  for (int i = 0; i < range_cnt; i++){
    int l = get<0>(path[i]);
    int r = get<1>(path[i]);
    int id = get<2>(path[i]);
    ccnt[l]++;
    l = start[l] + ccnt[l];
    r = start[r] + cnt[r];
    range[i] = make_tuple(l, r, id);
    id_max = max(id_max, l);
  }
  vector<int> R(id_max + 1);
  vector<int> pos(id_max + 1);
  for (int i = 0; i < range_cnt; i++){
    int l = get<0>(range[i]);
    int r = get<1>(range[i]);
    R[l] = r;
    pos[l] = i;
  }
  segment_tree ST(R);
  int Q;
  cin >> Q;
  long long S = 0;
  vector<bool> used(M, false);
  for (int i = 0; i < Q; i++){
    long long X;
    cin >> X;
    long long T = X ^ S;
    T--;
    long long ans = 0;
    if (!tree[T]){
      if (!used[T]){
        used[T] = true;
        ans += T + 1;
      }
    } else {
      ans += T + 1;
      if (B[T] == p[A[T]]){
        swap(A[T], B[T]);
      }
      int id = HLD[B[T]];
      while (true){
        pair<int, int> P = ST.range_max(0, start[id] + cnt[id]);
        if (P.first <= start[id] + cnt[id]){
          break;
        }
        int id2 = P.second;
        ST.update(id2);
        int edge_id = get<2>(range[pos[id2]]);
        if (!used[edge_id]){
          used[edge_id] = true;
          ans += edge_id + 1;
        }
      }
    }
    cout << ans << "\n";
    S = ans;
  }
}

想定はマージテクだったようで、コンテスト後に struct を使わないで複数テストケースだと大変だろとのいみさんに言われたので、それに対応した実装もしました。

atcoder.jp

#include <bits/stdc++.h>
using namespace std;
void dfs1(vector<vector<int>> &c, vector<int> &sz, int v = 0){
  for (int &w : c[v]){
    dfs1(c, sz, w);
    sz[v] += sz[w];
    if (sz[w] > sz[c[v][0]]){
      swap(w, c[v][0]);
    }
  }
}
void dfs2(vector<vector<int>> &c, vector<int> &in, vector<int> &next, 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, in, next, t, w);
  }
}
pair<int, int> st_get(vector<pair<int, int>> &ST, int L, int R, int i, int l, int r){
  if (r <= L || R <= l){
    return make_pair(-1, -1);
  } else if (L <= l && r <= R){
    return ST[i];
  } else {
    int m = (l + r) / 2;
    return max(st_get(ST, L, R, i * 2 + 1, l, m), st_get(ST, L, R, i * 2 + 2, m, r));
  }
}
int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int t = 1;
  for (int i = 0; i < t; i++){
    int N, M;
    cin >> N >> M;
    vector<int> A(M), B(M), C(M);
    for (int j = 0; j < M; j++){
      cin >> A[j] >> B[j] >> C[j];
      A[j]--;
      B[j]--;
    }
    vector<tuple<int, int, int, int>> E(M);
    for (int j = 0; j < M; j++){
      E[j] = make_tuple(C[j], A[j], B[j], j);
    }
    sort(E.begin(), E.end());
    vector<bool> tree(M);
    vector<vector<pair<int, int>>> E2(N);
    vector<int> UF_p(N, -1);
    for (int j = 0; j < M; j++){
      int a = get<1>(E[j]);
      int b = get<2>(E[j]);
      int id = get<3>(E[j]);
      int a2 = a;
      while (UF_p[a2] >= 0){
        a2 = UF_p[a2];
      }
      int b2 = b;
      while (UF_p[b2] >= 0){
        b2 = UF_p[b2];
      }
      int a3 = a;
      while (UF_p[a3] >= 0){
        int tmp = UF_p[a3];
        UF_p[a3] = a2;
        a3 = tmp;
      }
      int b3 = b;
      while (UF_p[b3] >= 0){
        int tmp = UF_p[b3];
        UF_p[b3] = b2;
        b3 = tmp;
      }
      if (a2 == b2){
        tree[id] = false;
      } else {
        tree[id] = true;
        if (UF_p[a2] < UF_p[b2]){
          swap(a2, b2);
        }
        UF_p[b2] += UF_p[a2];
        UF_p[a2] = b2;
        E2[a].push_back(make_pair(b, id));
        E2[b].push_back(make_pair(a, id));
      }
    }
    vector<int> p(N, -1);
    vector<vector<int>> c(N);
    queue<int> q;
    q.push(0);
    while (!q.empty()){
      int v = q.front();
      q.pop();
      for (auto P : E2[v]){
        int w = P.first;
        if (w != p[v]){
          p[w] = v;
          c[v].push_back(w);
          q.push(w);
        }
      }
    }
    vector<int> sz(N, 1);
    dfs1(c, sz);
    vector<int> in(N);
    vector<int> next(N, 0);
    int time = 0;
    dfs2(c, in, next, time);
    vector<tuple<int, int, int>> path;
    for (int j = 0; j < M; j++){
      if (!tree[j]){
        int u1 = A[j], v1 = B[j];
        int w;
        while (true){
          if (in[u1] > in[v1]){
            swap(u1, v1);
          }
          if (next[u1] == next[v1]){
            w = u1;
            break;
          }
          v1 = p[next[v1]];
        }
        int u2 = A[j], v2 = B[j];
        while (next[u2] != next[w]){
          path.push_back(make_tuple(in[next[u2]], in[u2] + 1, j));
          u2 = p[next[u2]];
        }
        path.push_back(make_tuple(in[w] + 1, in[u2] + 1, j));
        while (next[v2] != next[w]){
          path.push_back(make_tuple(in[next[v2]], in[v2] + 1, j));
          v2 = p[next[v2]];
        }
        path.push_back(make_tuple(in[w] + 1, in[v2] + 1, j));
      }
    }
    sort(path.begin(), path.end());
    int range_cnt = path.size();
    vector<int> cnt(N + 1, 0);
    for (int j = 0; j < range_cnt; j++){
      int l = get<0>(path[j]);
      cnt[l]++;
    }
    vector<int> start(N + 1);
    start[0] = 0;
    for (int j = 0; j < N; j++){
      start[j + 1] = start[j] + cnt[j] + 1;
    }
    vector<tuple<int, int, int>> range(range_cnt);
    vector<int> ccnt(N + 1, -1);
    int id_max = 0;
    for (int j = 0; j < range_cnt; j++){
      int l = get<0>(path[j]);
      int r = get<1>(path[j]);
      int id = get<2>(path[j]);
      ccnt[l]++;
      l = start[l] + ccnt[l];
      r = start[r] + cnt[r];
      range[j] = make_tuple(l, r, id);
      id_max = max(id_max, l);
    }
    vector<int> R(id_max + 1);
    vector<int> pos(id_max + 1);
    for (int j = 0; j < range_cnt; j++){
      int l = get<0>(range[j]);
      int r = get<1>(range[j]);
      R[l] = r;
      pos[l] = j;
    }
    int N2 = 1;
    while (N2 <= id_max){
      N2 *= 2;
    }
    vector<pair<int, int>> ST(N2 * 2 - 1, make_pair(-1, -1));
    for (int j = 0; j <= id_max; j++){
      ST[N2 - 1 + j] = make_pair(R[j], j);
    }
    for (int j = N2 - 2; j >= 0; j--){
      ST[j] = max(ST[j * 2 + 1], ST[j * 2 + 2]);
    }
    int Q;
    cin >> Q;
    long long S = 0;
    vector<bool> used(M, false);
    for (int j = 0; j < Q; j++){
      long long X;
      cin >> X;
      long long T = X ^ S;
      T--;
      long long ans = 0;
      if (!tree[T]){
        if (!used[T]){
          used[T] = true;
          ans += T + 1;
        }
      } else {
        ans += T + 1;
        if (B[T] == p[A[T]]){
          swap(A[T], B[T]);
        }
        int id = in[B[T]];
        while (true){
          pair<int, int> P = st_get(ST, 0, start[id] + cnt[id], 0, 0, N2);
          if (P.first <= start[id] + cnt[id]){
            break;
          }
          int id2 = P.second;
          int tmp = id2 + N2 - 1;
          ST[tmp] = make_pair(-1, -1);
          while (tmp > 0){
            tmp = (tmp - 1) / 2;
            ST[tmp] = max(ST[tmp * 2 + 1], ST[tmp * 2 + 2]);
          }
          int edge_id = get<2>(range[pos[id2]]);
          if (!used[edge_id]){
            used[edge_id] = true;
            ans += edge_id + 1;
          }
        }
      }
      cout << ans << "\n";
      S = ans;
    }
  }
}

E 問題

Nachia さんが dp[i] = (区間 [0,i) についての答え) という DP を考えていたので、遷移をいもす法で調べました。

atcoder.jp

#include <bits/stdc++.h>
using namespace std;
const long long MOD = 998244353;
int main(){
  int N;
  cin >> N;
  vector<int> P(N);
  for (int i = 0; i < N; i++){
    cin >> P[i];
    P[i]--;
  }
  vector<int> Q(N);
  for (int i = 0; i < N; i++){
    Q[P[i]] = i;
  }
  vector<vector<int>> imos(N + 1, vector<int>(N + 1, 0));
  for (int i = 0; i < N - 1; i++){
    vector<bool> c(N);
    for (int j = 0; j < N; j++){
      if (P[j] <= i){
        c[j] = false;
      } else {
        c[j] = true;
      }
    }
    vector<tuple<int, int, bool>> rle;
    rle.push_back(make_tuple(0, 1, c[0]));
    for (int j = 1; j < N; j++){
      if (c[j] == c[j - 1]){
        get<1>(rle.back())++;
      } else {
        rle.push_back(make_tuple(j, j + 1, c[j]));
      }
    }
    int cnt = rle.size();
    for (int j = 0; j < cnt - 1; j++){
      if (!get<2>(rle[j]) && get<2>(rle[j + 1])){
        int L1 = get<0>(rle[j]);
        int R1 = get<1>(rle[j]);
        int L2 = get<0>(rle[j + 1]);
        int R2 = get<1>(rle[j + 1]);
        imos[L1][R1]++;
        imos[L1][R2]--;
        imos[L2][R1]--;
        imos[L2][R2]++;
      }
    }
  }
  for (int i = 0; i < N; i++){
    for (int j = 0; j < N; j++){
      imos[i][j + 1] += imos[i][j];
    }
  }
  for (int i = 0; i < N; i++){
    for (int j = 0; j < N; j++){
      imos[i + 1][j] += imos[i][j];
    }
  }
  vector<long long> dp(N + 1, 0);
  dp[0] = 1;
  for (int i = 0; i < N; i++){
    for (int j = i + 1; j <= N; j++){
      if (imos[i][j - 1] == 0){
        dp[j] += dp[i];
        if (dp[j] >= MOD){
          dp[j] -= MOD;
        }
      }
    }
  }
  cout << dp[N] << endl;
}

平面走査をしてこれをデータ構造で高速化することを考えましたが、セグ木では処理できない形のクエリになってしまいました。