A - Adjacent Difference

Hint 1

例えば $A_{i,j}$ がすべて $0$ で，$d=1$ の場合にはどうすればよいでしょうか．

Hint 2

$k$ を定数として，$i+j$ が偶数ならば $A_{i,j}=k$，$i+j$ が奇数ならば $A_{i,j}=k+d$ が成り立つようにすると，隣接する $2$ マスに書き込まれている整数の差は $d$ 以上になります．

Hint 3

$k$ を定数として，$i+j$ が偶数ならば $A_{i,j}\equiv k\pmod{2d}$，$i+j$ が奇数ならば $A_{i,j}\equiv k+d\pmod{2d}$ が成り立つようにすると，隣接する $2$ マスに書き込まれている整数の差は $d$ 以上になります．

解説 → https://atcoder.jp/contests/agc066/editorial/9566

---

B - Decreasing Digit Sums

Hint 1

$5^{50}$ の倍数を利用するのが簡潔な構成方法だと思います．

Hint 2

適当な $n$ に対して $x=5^{50}n$ とすると，$2^ix=10^i\cdot 5^{50-i}n$ は多くの $n$ に対して，単調減少とまではいかないものの，$5^{50-i}n$ の桁数の減少に応じた減少傾向がありそうです．

Hint 3

減少傾向のある列を複数作り，足し合わせて平均化することで，単調減少な列を作りましょう．

解説 → https://atcoder.jp/contests/agc066/editorial/9567

---

C - Delete AAB or BAA

Hint 1

このような問題でのよくある解法として，先頭 $i$ 文字を操作後に最小何文字にできるかを $\mathrm{dp}[i]$ とする動的計画法があります．最後の文字を消去しない場合の遷移 $\mathrm{dp}[i]\leftarrow \mathrm{dp}[i-1]+1$ に加え，$S[i]\cdots S[j-1]$ 部分が完全に消去できるならば $\mathrm{dp}[j] \leftarrow \mathrm{dp}[i]$ という遷移があります．

Hint 2

文字列が完全に消去できるための条件を考えることが課題となります．簡単な必要条件として，A の個数がB の個数の $2$ 倍であることが必要です．これに加えて条件がもうひとつ必要です．

Hint 3

完全に消去できる文字列は，次を満たす部分文字列に分割することができます：A の個数がB の個数の $2$ 倍であり，左端または右端は B である．

解説 → https://atcoder.jp/contests/agc066/editorial/9568

---

D - A Independent Set

Hint 1

$O(N^2)$ 状態の dp を考えることは簡単にできます．最適解の構造を考えることで，考えるべき状態数を $O(N)$ に減らすことができます．

Hint 2

操作後の文字列を $T$ とします．末尾に B をつけると，$T$ は AB，B を並べたものとなります．AB，B をスワップすることを考えて，最適解 $T$ について言えることを考えましょう．

Hint 3

参考画像

解説 → https://atcoder.jp/contests/agc066/editorial/9569

---

E - Sliding Puzzle On Tree

Hint 1

次数 $3$ 以上の点 $u$ に石がなく，$u$ の近傍にも石がない頂点があるとき，$u$ の近傍にある石同士を自由にスワップできます．

Hint 2

どの次数 $3$ 以上の点の周りのスワップに関われるかによって，石全体をいくつかの同値類に分けることができます．

Hint 3

$K=N,N-1,\ldots$ 順に計算することにすると，石の削除 と同値類の合併をすることになり，UnionFind を使って必要な計算を行うことができます．

解説 → https://atcoder.jp/contests/agc066/editorial/9570

---

F - Beautiful String

Hint 1

長さ \(N\) の美しい文字列は \(3\cdot 2^{N-1}\) 通りあり，差分の列を考えることにより，先頭の文字と長さ \(N-1\) の \(2\) 値の文字列の組と対応させることができます．

Hint 2

まずは先頭 \(2\) 文字，末尾 \(2\) 文字のスワップを禁止した場合が比較的簡単に解けると思います．その場合を解いたあと，先頭 \(2\) 文字，末尾 \(2\) 文字操作を考慮するとよいでしょう．

解説 → https://atcoder.jp/contests/agc066/editorial/9417