AtCoder Beginner Contest 450

A - 3,2,1,GO

Very easy.

ABC450_A

1 2	n = int(input()) print(','.join([str(i) for i in range(n, 0, -1)]))

B - Split Ticketing

Just a simple $O(N^3)$ loop.

ABC450_B

#include <bits/stdc++.h>

int main() {
  std::cin.tie(0)->sync_with_stdio(false), std::cout.tie(0);

  int n;
  std::cin >> n;

  std::vector g(n, std::vector<int>(n + 1, 0));
  for (int i = 1; i <= n - 1; i++) {
    for (int j = i + 1; j <= n; j++)
      std::cin >> g[i][j];
  }

  for (int i = 1; i < n - 1; i++) {
    for (int j = i + 1; j < n; j++) {
      for (int k = j + 1; k <= n; k++) {
        if (g[i][j] + g[j][k] < g[i][k]) {
          std::cout << "Yes\n";
          return 0;
        }
      }
    }
  }

  std::cout << "No\n";
}

C - Puddles

DFS 或者 BFS 都可以解．拓展到一个新格子时，检查是否在边界即可．

ABC450_C

#include <bits/stdc++.h>

using pair = std::pair<int, int>;
std::array<std::pair<int, int>, 4> next{pair{1, 0}, pair{-1, 0}, pair{0, 1},
                                        pair{0, -1}};

int main() {
  std::cin.tie(0)->sync_with_stdio(false), std::cout.tie(0);

  int h, w;
  std::cin >> h >> w;

  std::vector g(h + 1, std::vector<char>(w + 1, ' '));
  for (int i = 1; i <= h; i++)
    for (int j = 1; j <= w; j++)
      std::cin >> g[i][j];

  std::vector vis(h + 1, std::vector<int>(w + 1, 0));
  auto is_open = [&](int row, int col) {
    return row == 1 or row == h or col == 1 or col == w;
  };
  auto search = [&](int row, int col) {
    std::queue<std::pair<int, int>> q;
    q.push({row, col});
    bool opn = false;
    while (!q.empty()) {
      auto [ph, pw] = q.front();
      q.pop();
      if (vis[ph][pw])
        continue;
      vis[ph][pw] = true;
      opn |= is_open(ph, pw);

      for (const auto &[dx, dy] : next) {
        int nx = ph + dx, ny = pw + dy;
        if (nx <= 0 or nx > h or ny <= 0 or ny > w or g[nx][ny] == '#')
          continue;
        q.push({nx, ny});
      }
    }

    return opn;
  };

  int ans = 0;
  for (int i = 1; i <= h; i++) {
    for (int j = 1; j <= w; j++) {
      if (g[i][j] == '#' || vis[i][j])
        continue;
      if (!search(i, j))
        ans++;
    }
  }
  std::cout << ans << "\n";
}

D - Minimize Range

Suppose we always sort they array $a[]$ increasingly. Then $\min a=a_1, \max a=a_{n}$

First of all, we can always conclude that $\max-\min < k$ , because otherwise, we can add $k$ to $a_1$ to decrease the difference. This gives $a_1+k>a_n$ .

Now, the minimum possible answer can only be attained by increasing $a_1$ , because if we add $k$ to $a_2$ , then either the difference remains the same, or $a_2+k>a_n$ and the difference cannot be smaller. Given that $a_1+k>a_n$ , it’ll take at most $O(n)$ times of $+k$ operation to increase all elements by $k$ .

So we can use an ordered set to keep track of the order. The time complexity is $O(n\log n)$ .

ABC450_D

#include <bits/stdc++.h>

using i64 = long long;

int main() {
  std::cin.tie(0)->sync_with_stdio(false), std::cout.tie(0), std::cerr.tie(0);
  i64 n, k;
  std::cin >> n >> k;

  std::vector<i64> a(n);
  for (auto &x : a)
    std::cin >> x;
  i64 max = *std::max_element(a.begin(), a.end());
  for (auto &x : a)
    x += (max - x) / k * k;

  std::multiset<i64> f(a.begin(), a.end());
  i64 ans = 1e18;
  for (int i = 0; i < 2 * n; i++) {
    ans = std::min(ans, *f.rbegin() - *f.begin());
    auto x = *f.begin();
    f.erase(f.begin());
    f.insert(x + k);
  }

  std::cout << ans << "\n";
}

E - Fibonacci String

The first step is straightforward. Suppose we have a function $f_c(p)$ that tells the number of character $c$ in $s[1,p]$ . Then the answer is just $f_c(r)-f_c(l-1)$ .

So the next step is to compute $f_c(p)$ efficiently given $c,p$ . Note that $s_i$ is formed by concatting $s_{i-1}, s_{i-2}$ . So, by binary searching on length of $s_i$ , we can locate $p$ . Suppose we know that some $i$ satisfies $s_{i-1}\le p\lt s_{i}$ , then we can simply add $count(s_{i-1}, c)$ to the final answer, and reduce $p$ to search on $s_{i-2}$ .

This gives a $O(\log L)$ solution for a single $f_c(p)$ . So the total complexity is $O(Q\log L)$

ABC450_E

#include <algorithm>
#include <bits/stdc++.h>

using i64 = long long;

auto cvt = [](char f) { return f - 'a'; };

int main() {
  std::cin.tie(0)->sync_with_stdio(false), std::cout.tie(0), std::cerr.tie(0);
  std::string x, y;
  std::cin >> x >> y;
  int q;
  std::cin >> q;

  std::vector<i64> len{(i64)x.length(), (i64)y.length()};
  std::array<std::vector<i64>, 30> cnt;
  for (int i = 0; i < 26; i++) {
    cnt[i].push_back(std::count(x.begin(), x.end(), i + 'a'));
    cnt[i].push_back(std::count(y.begin(), y.end(), i + 'a'));
  }
  while (len.back() < 1e18) {
    int t = len.size();
    len.push_back(len[t - 1] + len[t - 2]);
    for (int i = 0; i < 26; i++)
      cnt[i].push_back(cnt[i][t - 1] + cnt[i][t - 2]);
  }

  auto solve = [&](auto self, i64 pos, char c, i64 level) -> i64 {
    if (pos == 0)
      return 0;
    if (level == 0) {
      assert(pos <= x.length());
      return std::count(x.begin(), x.begin() + pos, c);
    }
    auto index =
        std::upper_bound(len.begin() + 1, len.end(), pos) - len.begin() - 1;
    if (level == 1 || index == 0) {
      assert(pos <= y.length());
      return std::count(y.begin(), y.begin() + pos, c);
    }
    return self(self, pos - len[index], c, index - 1) + cnt[cvt(c)][index];
  };

#define SOLVE(p, c, l) solve(solve, p, c, l)

  while (q--) {
    i64 l, r;
    char k;
    std::cin >> l >> r >> k;
    std::cout << SOLVE(r, k, 1e18) - SOLVE(l - 1, k, 1e18) << "\n";
  }
}

F - Strongly Connected 2

Assume we have sorted edges by src point. One observation is that, since $i$ can reach $j$ if $i\gt j$ , so $1\sim s$ is SCC iff $1$ can reach $s$ . Let $dp[i][s]$ be the number of solution to make $1\sim s$ be strongly connected by only considering the first $i$ edges.

Initially, all $dp[0][s]=0$ except that $dp[0][1]=1$ . Now consider edge $(x_i, y_i)$ ,

For $s\lt x_i$ or $s\gt y_i$ , whether accept or reject this edge does not affect the existing solutions. So $dp[i][s]\gets 2dp[i-1][s]$
For $x_i\le s\lt y_i$ , we must not accept this edge, because it will make existing solutions able to reach nodes larger than $s$ . So $dp[i][s]\gets dp[i-1][s], s\in [x_i, y_i)$
However, for $s=y_i$ , this edge enables more solutions which end at $p\in[x_i, y_i]$ . So $dp[i][s]\gets dp[i-1][s]+\sum_{p\in[x_i,y_i]} dp[i-1][p]$

We can do in-place modification with segment tree. So the total complexity is $O(n\log n)$ .

ABC450_F

#include <bits/stdc++.h>

constexpr int Mod = 998244353;
struct mint {
  int v;
  mint(int _v) : v{_v} {}
  mint operator+(mint r) const {
    return v + r.v >= Mod ? v + r.v - Mod : v + r.v;
  }
  mint operator+=(mint r) { return *this = *this + r; }
  mint operator*(mint r) const { return 1ll * v * r.v % Mod; }
  mint operator*=(mint r) { return *this = *this * r; }
};

struct segment {
  std::vector<mint> T, tag;
  int tot;

  void init(int n) {
    T.resize(n * 4 + 10, 0);
    tag.resize(n * 4 + 10, 1);
    tot = n;
  }
  void add(int pos, int v) { add(pos, v, 1, 1, tot); }
  void multiply(int l, int r) {
    if (r >= l)
      multiply(l, r, 1, 1, tot);
  }
  int sum_over(int l, int r) {
    return r >= l ? sum_over(l, r, 1, 1, tot).v : 0;
  }
  int at(int i) { return sum_over(i, i, 1, 1, tot).v; }

private:
  void push_down(int p) {
    if (tag[p].v == 1)
      return;
    T[p << 1] *= tag[p], T[p << 1 | 1] *= tag[p];
    tag[p << 1] *= tag[p], tag[p << 1 | 1] *= tag[p];
    tag[p] = 1;
  }
  void pull_up(int p) { T[p] = T[p << 1] + T[p << 1 | 1]; }
  void add(int pos, mint v, int p, int l, int r) {
    if (l == r) {
      T[p] += v;
      return;
    }
    push_down(p);
    int mid = l + ((r - l) >> 1);
    pos <= mid ? add(pos, v, p << 1, l, mid)
               : add(pos, v, p << 1 | 1, mid + 1, r);
    pull_up(p);
  }
  void multiply(int L, int R, int p, int l, int r) {
    if (r < L or R < l)
      return;
    if (L <= l and r <= R) {
      T[p] *= 2, tag[p] *= 2;
      return;
    }
    int mid = l + ((r - l) >> 1);
    push_down(p);
    multiply(L, R, p << 1, l, mid);
    multiply(L, R, p << 1 | 1, mid + 1, r);
    pull_up(p);
  }
  mint sum_over(int L, int R, int p, int l, int r) {
    if (r < L or R < l)
      return 0;
    if (L <= l and r <= R)
      return T[p];
    push_down(p);
    int mid = l + ((r - l) >> 1);
    return sum_over(L, R, p << 1, l, mid) +
           sum_over(L, R, p << 1 | 1, mid + 1, r);
  }
};

int main() {
  std::cin.tie(0)->sync_with_stdio(false), std::cout.tie(0),
  std::cerr.tie(0);
  int n, m;
  std::cin >> n >> m;

  segment s;
  s.init(n);
  s.add(1, 1);
  std::vector<std::pair<int, int>> v(m);
  for (auto &[x, y] : v)
    std::cin >> x >> y;

  std::sort(v.begin(), v.end());
  for (auto [x, y] : v) {
    // r < x or r > y
    s.multiply(1, x - 1);
    s.multiply(y + 1, n);
    // r = y
    s.add(y, s.sum_over(x, y));
  }
  std::cout << s.sum_over(n, n) << "\n";
}

G - Random Subtraction

A better solution