A - Inside or Outside

Hint 1

First, check whether you can achieve the goal at cost $2$ or less.

Hint 2

If $M \ge 3$, then you can always achieve the goal at cost $3$ or less.

Editorial: https://atcoder.jp/contests/arc190/editorial/11919

---

B - L Partition

Hint 1

The condition “an L-shape of level $k$ is placed” is more complicated than the condition “an L-shape of level up to $k$ is placed.” So handle the latter first.

Hint 2

The counting separates independently into vertical and horizontal parts.

Editorial: https://atcoder.jp/contests/arc190/editorial/11920

---

C - Basic Grid Problem with Updates

Hint 1

It is natural to consider $\mathrm{dp}[h][w]$, which is the sum of $f(P)$ over paths whose endpoint is $(h,w)$. When a cell’s value changes, the values before that cell don’t need to be updated, but everything from that cell onward does.

Hint 2

Also consider $\mathrm{dp}_2[h][w]$ for paths from $(h,w)$ to $(H,W)$. You can maintain $\mathrm{dp}$ for the parts before the changed cell and $\mathrm{dp}_2$ for the parts after the changed cell.

Editorial: https://atcoder.jp/contests/arc190/editorial/11921

---

D - Matrix Pow Sum

Hint 1

Consider replacing each 0 in the matrix by an indeterminate and then taking the $p$-th power. For instance, in Sample Input 1: $$\begin{pmatrix}x_{11}&1\\\ x_{21}&2\end{pmatrix}^3=\begin{pmatrix}x_{11}^3+2x_{11}x_{21}+2x_{21}&x_{11}^2+2x_{11}+x_{21}+4\\\ x_{11}^2x_{21}+x_{21}^2+2x_{11}x_{21}+4x_{21}&x_{11}x_{21}+4x_{21}+8\end{pmatrix}$$

Hint 2

Summing over all possibilities of substituting $1, 2, \ldots, p-1$ for each indeterminate amounts to a non-zero sum only in terms where every indeterminate appears with exponent $(p-1)$.

Hint 3

Beware of corner cases when $p=2$ or $p=3$.

Editorial: https://atcoder.jp/contests/arc190/editorial/11922

---

E - Gaps of 1 or 2

Hint 1

This problem can be formulated as a maximum matching problem in a graph.

Hint 2

Consider using the [Tutte-Berge formula](https://en.wikipedia.org/wiki/Tutte%E2%80%93Berge_formula).

Hint 3

You can handle range queries by segment trees over matrices in the max-plus semiring, corresponding to a DP that multiplies a vector by a matrix.

Editorial: https://atcoder.jp/contests/arc190/editorial/11923