公式

E - Gaps of 1 or 2 解説 by evima

Hint → https://atcoder.jp/contests/arc190/editorial/11918

[1] Strategy

First, ignore the range queries and consider the case where \(Q=1\), \(L=1\), and \(R=N\).

We can formulate the problem as a maximum matching problem on a graph:

There are \(A_i\) vertices at coordinate \(i\). If \(1 \le j - i \le 2\), connect every vertex at coordinate \(i\) to every vertex at coordinate \(j\). Find the size of the maximum matching in this graph.

We can try to use the Tutte-Berge formula to find this maximum matching. Then we seek to solve the problem of maximizing \(\mathrm{odd}(G-U)-|U|\) by appropriately choosing a vertex set \(U\).

In this situation, we can prove that there is an optimal solution with the following property: either all vertices at coordinate \(i\) are included in \(U\) or none of them are.

This can be proved by fixing inclusion/exclusion for vertices at coordinates other than \(i\), then adding from \(0\) up to \(A_i - 1\) vertices at coordinate \(i\) into \(U\).

As a result, the problem reduces to searching over \(2^N\) ways of including or not including all vertices of each coordinate \(i\) in \(U\), to find an optimal one.

[2] Calculation details

Let \(u_i = 1\) if all vertices at coordinate \(i\) are included in \(U\), and \(u_i = 0\) otherwise, to define a binary sequence \((u_1,\ldots,u_N)\).

For convenience, let \(u_0 = u_{N+1} = 1\), etc.

The sequence \((u_i)\) in question and \(\mathrm{odd}(G-U) - |U|\) for that sequence can be computed as follows.

  • We can assume the sequence \((u_i)\) does not contain the contiguous subsequence \((0,1,0)\).
    • This is because replacing that middle \(1\) by \(0\) is never worse.
  • When \(u_i = 1\), we gain \(-A_i\) points.
    • This corresponds to \(-|U|\).
  • When \(u_{i-1}=1, u_i=0, u_{i+1}=1\), we gain \(+A_i\) points.
    • This corresponds to \(A_i\) isolated vertices (odd components).
  • When \(u_{L-1}=1\), \(u_L = \cdots = u_R = 0\), \(u_{R+1}=1\), and \(R>L\), we gain \(1\) point if \(A_L + \cdots + A_R\) is odd.

If \(A_i=0\) for some \(i\), the above formula may not strictly represent \(\mathrm{odd}(G-U)-|U|\). However, this computation is fine because of reasons such as there being no benefit in merging with adjacent connected components when \(A_i=0\) and \(u_i=0\),

We consider setting the sequence \((u_i)\) in order from \(i=1\) to \(N\). By keeping as states whether there are two or more trailing zeros or ones, and the parity of the sum of \(A\) in a block of consecutive zeros, etc., a DP with \(O(1)\) states can compute the answer to the problem in \(O(N)\) time.

[3] Handling queries

The above DP can be described as successively multiplying a vector by a suitable \(K \times K\) matrix (over the max-plus semiring). Thus, for range queries, we can use a segment tree.

If the DP can be described by a \(K \times K\) matrix, we can use a segment tree to handle products of \(K \times K\) matrices to solve the problem in \(O((N + Q\log N)K^3)\) time. In the author’s implementation, \(K=5\), for which the complexity is small enough.

Since there are no updates to the sequence \(A\) in this problem, the segment tree will not be modified. The query is effectively computing \(X M_1 \cdots M_n\) for a row vector \(X\) and matrices \(M_1,\ldots,M_n\), and this can be done from left to right as repeated vector-matrix products (rather than matrix-matrix products). This method has a complexity of \(O(NK^3 + QK^2 \log N)\), which is likely fine even if \(K\) is somewhat larger than in the author’s code. Another speed-up is to use the sparseness of the transition matrix and divide-and-conquer, instead of a segment tree.

[4] Comments

The Tutte-Berge formula is a well-known theorem in the topic of maximum matching for general graphs, familiar to many who have studied this area. The idea of combining that theorem with DP to compute a maximum matching feels very natural.

However, the author has never seen such a solution in programming contests. If you know problems that expect a similar method, please let us know.

投稿日時:
最終更新: