AtCoder Beginner Contest 331

基本情况

第一次打这个，感觉跟CF有点不一样。

A题秒了。

B题就完全背包变种秒了。

C题简单模拟，秒了。

D题明显是二位前缀和，但是后面处理总感觉有点麻烦，就先调到E。

E题做出来了，但是不如标程，所以贴一下标程。

D - Tile Pattern

We define a function \(f(A, B, C, D)\) as follows. (Notice the presence/absence of equal sign in each inequality sign.)

\(f(A, B, C, D) =\) (the number of black squares among those squares \((h, w)\) with \(A \leq h \lt C\) and \(B \leq w \lt D\)).

The sought value is \(f(A, B, C + 1, D + 1)\). (Note the shift by \(1\).)
While one can directly implement an algorithm that directly evaluates \(f\), the implementation requires a bunch of caseworks because there are four arguments, so we try to avoid it.

What we want is the (d) part:

editorial1

By exploiting a technique on cumulative sums, we can express it as follows:

\[ \begin{aligned} &f(A, B, C, D) \\ &=(\text{The number of black squares in }(d)) \\ &= (\text{The number of black squares in }(a), (b), (c), (d)) \\ &- (\text{The number of black squares in }(a), (b)) \\ &- (\text{The number of black squares in }(a), (c)) \\ &+ (\text{The number of black squares in }(a)) \\ &= f(0, 0, C, D) - f(0, 0, C, B) - f(0, 0, A, D) + f(0, 0, A, B) \end{aligned} \]

With this deformation, we can constrain the arguments of \(f\) so that \(A=B=0\). That is, if we define

\(g(H, W) =\) (the number of black squares among those squares \((h, w)\) with \(0 \leq h \lt H\) and \(0 \leq w \lt W\)),

it holds that

\[ f(A,B,C,D) = g(C,D) - g(C, B) - g(A, D) + g(A, B), \]

so all that left is to implement \(g\), which has only two arguments.

Now we consider how to evaluate \(g(H, W)\). A naive implementation would cost too much time, so we want to make use of the periodicity.
For example, when \(H = 8, W = 7\), and \(N = 3\), one can divide the grid by period as follows:

editorial2

Since the grid has \((3 \times 3)\) periodic pattern, the sub-rectangles are classified into the following four types, all of which coincide with or are smaller than \(N \times N\):

\(4\) rectangles of type A whose pattern coincides with the top-left \(3 \times 3\) region
\(2\) rectangles of type B whose pattern coincides with the top-left \(2 \times 3\) region
\(2\) rectangles of type C whose pattern coincides with the top-left \(3 \times 1\) region
\(1\) rectangles of type D whose pattern coincides with the top-left \(2 \times 1\) region

This holds for a general \(H, W, N\), so the problem can be simplified if we know the number of rectangles of the four types and their dimensions. These can be obtained as the quotients and remainders when \(H\) and \(W\) are divided by \(N\).

Therefore, by precomputing \(g(i, j)\) for all \(0 \leq i \leq N, 0 \leq j \leq N\), the problem can be solved in \(\mathrm{O}(1)\) time per query.
The percomputation can be done by applying the technique used for the first figure again, in order to obtain the following recurrence relation:

\[ \begin{aligned} g(i, j) &= (1\text{ if } ((i-1,j-1)\text{ is a black square}) \text{ else } 0) \\ &+ g(i - 1, j) + g(i, j - 1) - g(i - 1, j - 1). \end{aligned} \]

Thus, the precalculation can be done in a total of \(\mathrm{O}(N^2)\) time. (If \(i = 0\) or \(j = 0\), let \(g(i, j) = 0\).)
Therefore, the problem has been solved in a total of \(\mathrm{O}(N^2 + Q)\) time, which is fast enough.

Sample code (C++)

#include <iostream>
#include <string>
#include <vector>
using namespace std;

int N, Q, precalc[1010][1010];

long long g(int H, int W) {
  if (H <= N and W <= N) return precalc[H][W];
  int Hq = H / N, Hr = H % N;
  int Wq = W / N, Wr = W % N;
  long long ret = 0;
  ret += g(N, N) * Hq * Wq;
  ret += g(Hr, N) * Wq;
  ret += g(N, Wr) * Hq;
  ret += g(Hr, Wr);
  return ret;
}

long long f(int A, int B, int C, int D) {
  return g(C, D) - g(A, D) - g(C, B) + g(A, B);
}

int main() {
  cin >> N >> Q;
  vector<string> S(N);
  for (auto& s : S) cin >> s;
  for (int i = 1; i <= N; i++) {
    for (int j = 1; j <= N; j++) {
      precalc[i][j] += S[i - 1][j - 1] == 'B';
      precalc[i][j] += precalc[i - 1][j];
      precalc[i][j] += precalc[i][j - 1];
      precalc[i][j] -= precalc[i - 1][j - 1];
    }
  }
  while (Q--) {
    int A, B, C, D;
    cin >> A >> B >> C >> D;
    cout << f(A, B, C + 1, D + 1) << "\n";
  }
}

E - Set Meal

There are several approaches to this problem. In this editorial, we explain one that uses a priority queue.

First of all, we outline the algorithm as follows:

Repeat the following operations until an available meal is found.
- Find (somehow) a pair of main dish and side dish with the highest price among those not enumerated yet.
- If a set meal with that pair is actually offered, print its price and terminate the entire procedure.

The repetition is performed at most \((L+1)\) times. Thus, once we construct a proper algorithm for the “somehow” above, the problem can be solved fast enough.

We describe how to find an unseen pair of main dish and side dish with the highest price fast.
For simplicity, we assume that \(b_1 \geq b_2 \geq \dots \geq b_M\) (otherwise, we can use the indices when \(b\) is sorted in descending order). Then, one can obtain a pair with the highest price by the following procedure.

Let cur be an auxiliary variable, which is an array of length \(N\). cur[i] maintains the index of side meal paired with main dish \(i\), initialized with cur[i] = 1.
Prepare a priority queue Q that stores (cost, index of main dish) and supports retrieval of one with the maximum cost.
For each \(i=1, 2, \dots, N\), insert \((a_i + b_1, i)\) to \(i\).
One can find a pair of main dish and side dish with the highest price among those not enumerated yet as follows:
- Let \((c,i)\) be the topmost element in \(Q\). Pop the topmost element from \(Q\). The sought pair with the highest price is \((i, \mathrm{cur}[i])\).
- Then, add \(1\) to cur[i].
- If cur[i] is no greater than \(M\), insert \((a_i + b_\mathrm{cur[i]}, i)\) into Q.

This algorithm is justified by proving the fact that Q always store an unseen pair with the maximum cost. If you know D’Hondt method in electoral system, it may be easier to consider it as a D’Hondt-method-like one.

By appropriately implement the algorithm above, the problem can be solved in a total of \(\mathrm{O}(L (\log N + \log L) + N + M \log M)\) time, which is fast enough.

#include <algorithm>
#include <iostream>
#include <queue>
#include <set>
#include <utility>
#include <vector>
using namespace std;
int main() {
  int N, M, L;
  cin >> N >> M >> L;
  vector<int> a(N), b(M);
  for (auto& x : a) cin >> x;
  for (auto& x : b) cin >> x;
  set<pair<int, int>> bad;
  for (int i = 0; i < L; i++) {
    int c, d;
    cin >> c >> d;
    bad.emplace(c - 1, d - 1);
  }

  vector<int> ord_b(M);
  for (int i = 0; i < M; i++) ord_b[i] = i;
  sort(begin(ord_b), end(ord_b), [&](int i, int j) { return b[i] > b[j]; });

  vector<int> cur(N);
  priority_queue<pair<int, int>> Q;
  for (int i = 0; i < N; i++) Q.emplace(a[i] + b[ord_b[cur[i]]], i);
  while (true) {
    auto [cost, i] = Q.top();
    int j = cur[i];
    Q.pop();
    if (bad.count({i, ord_b[j]}) == 0) {
      cout << cost << "\n";
      break;
    }
    cur[i]++;
    if (cur[i] != M) Q.emplace(a[i] + b[ord_b[cur[i]]], i);
  }
}