A - Union of Grid Paths

Hint 1

A cell $(x,y)$ can be painted black precisely if there exists a valid path from $(1,1)$ to $(x,y)$ and a valid path from $(x,y)$ to $(H,W)$.

Hint 2

Fix $k$, and consider how to count the number of pairs $(x,y)$ satisfying $x+y=k$.

Editorial: https://atcoder.jp/contests/arc197/editorial/12879

---

B - Greater Than Average

Hint 1

Look for a property you can assume of an optimal subsequence. To do so, identify operations on subsequences (adding, removing, or swapping elements) that never decrease the score.

Hint 2

If there is an unchosen element that is not greater than the current average, adding it does not decrease the score. Hence, you only need to consider cases where all elements not greater than the average are chosen.

Hint 3

What about elements that are not less than the average? Consider swapping a chosen element with an unchosen one.

Editorial: https://atcoder.jp/contests/arc197/editorial/12880

---

C - Removal of Multiples

Hint 1

The statement claims “it can be shown that $S$ has at least $B_i$ elements at this point.” First, think how to prove this.

Hint 2

The answer isn’t very large—you can show it’s at most about $3\times10^6$. Prepare a data structure supporting deletions and $k$-th-element retrievals up to that bound.

Hint 3

Be careful: repeatedly scanning multiples of the same number or deleting the same number many times can push your complexity to a higher order.

Editorial: https://atcoder.jp/contests/arc197/editorial/12881

---

D - Ancestor Relation

Hint 1

Rather than viewing the input as a matrix, think of it as a graph. First, consider what the ancestor-descendant graph of a rooted tree looks like.

Hint 2

Hint 3

To reconstruct the rooted tree from the input graph, repeat: “choose a vertex adjacent to all others as the root,” then “remove that root and split into connected components.”

Editorial: https://atcoder.jp/contests/arc197/editorial/12882

---

E - Four Square Tiles

Hint 1

The four tiles must occupy the top-left, top-right, bottom-left, and bottom-right positions.

Hint 2

First, count placements where no two adjacent tiles overlap. Then, subtract the overcounted cases.

Hint 3

If adjacent tiles do not overlap, both the “topleft-bottomright” and “topright-bottomleft” pairs cannot overlap simultaneously. So count cases where one specific non-adjacent pair overlaps. Organize the conditions to see that we can deal with rows and columns independently.

Editorial: https://atcoder.jp/contests/arc197/editorial/12883