A - Adjacent Difference

Hint 1

For example, if all $A_{i,j}$ are $0$ and $d=1$, what should you do?

Hint 2

Let $k$ be a constant. If we let $A_{i,j}=k$ if $i+j$ is even and $A_{i,j}=k+d$ if $i+j$ is odd, then the difference between the integers written in the two adjacent cells will be at least $d$.

Hint 3

Let $k$ be a constant. If we let $A_{i,j}\equiv k\pmod{2d}$ if $i+j$ is even and $A_{i,j}\equiv k+d\pmod{2d}$ if $i+j$ is odd, then the difference between the integers written in the two adjacent cells will be at least $d$.

Editorial: https://atcoder.jp/contests/agc066/editorial/9709

---

B - Decreasing Digit Sums

Hint 1

Using multiples of $5^{50}$ is a concise way to construct a solution.

Hint 2

By setting $x=5^{50}n$ for some $n$, $2^ix=10^i\cdot 5^{50-i}n$ seems to have a decreasing trend according to the decrease in the number of digits of $5^{50-i}n$ for many $n$, although it may not be strictly decreasing.

Hint 3

Let's create multiple sequences with a decreasing trend and average them by adding them together to create a strictly decreasing sequence.

Editorial: https://atcoder.jp/contests/agc066/editorial/9710

---

C - Delete AAB or BAA

Hint 1

A common solution for such problems is dynamic programming, where $\mathrm{dp}[i]$ represents the minimum possible number of characters after operations on the first $i$ characters. In addition to the transition $\mathrm{dp}[i]\leftarrow \mathrm{dp}[i-1]+1$ for not deleting the last character, there is a transition $\mathrm{dp}[j] \leftarrow \mathrm{dp}[i]$ if the substring $S[i]\cdots S[j-1]$ can be completely deleted.

Hint 2

The challenge is to consider the conditions for a string to be completely deletable. A simple necessary condition is that the number of As must be twice the number of Bs. In addition to this, another condition is needed.

Hint 3

A string that can be completely deleted can be divided into substrings that satisfy the following: the number of As is twice the number of Bs, and either the left or right end is B.

Editorial: https://atcoder.jp/contests/agc066/editorial/9711

---

D - A Independent Set

Hint 1

It is easy to consider a DP with $O(N^2)$ states. By thinking about the structure of the optimal solution, it is possible to reduce the number of states to $O(N)$.

Hint 2

Let $T$ be the string after the operation. If you add B to the end, $T$ becomes a sequence of AB and B. Consider swapping AB and B and think about what can be said about the optimal solution $T$.

Hint 3

See this image.

Editorial: https://atcoder.jp/contests/agc066/editorial/9712

---

E - Sliding Puzzle On Tree

Hint 1

When there is no stone on a vertex $u$ with degree $3$ or greater, and there is an empty vertex in the neighborhood of $u$, you can freely swap the stones in the neighborhood of $u$.

Hint 2

Depending on which vertices with degrees $3$ or higher a stone can be involved in swaps around, the stones can be divided into several equivalence classes.

Hint 3

If you compute the answer in the order $K=N,N-1,\ldots$, you will be doing stone deletion and merging of equivalence classes, which can be done using UnionFind.

Editorial: https://atcoder.jp/contests/agc066/editorial/9713

---

F - Beautiful String

Hint 1

There are \(3\cdot 2^{N-1}\) beautiful strings of length \(N\), and by considering the sequence of differences, it can be associated with a pair of the first character and a binary string of length \(N-1\).

Hint 2

First, it might be relatively easy to solve the case where swapping the first two or the last two characters is prohibited. After solving that case, you can consider operations involving the first two and the last two characters.

Editorial: https://atcoder.jp/contests/agc066/editorial/9714