A. Almost Equal
「隣接 $n$ 項の和」をすべて足すと，和は $n\cdot \frac{2n(2n+1)}{2}$ になります．
$n$ が偶数のときこれは $2n$ の倍数です．よって almost equal になるのは和が定数列にならざるを得ず，$[0,n)$ と $[1,n+1)$ の比較から矛盾します．
$n$ が奇数のとき，$A[i]$ と $A[n+i]$ の差が $1$ になるように作ることに注意してうまく構築します．
B. Shortest Cycle
$a_i=0$ は除いておきます．各 $a_i$ がひとつ以上 bit を持ちます．
bit は $60$ 種以下なので，$N>120$ だと，ある bit が $3$ 回使われて長さ $3$ のサイクル発生です．
$N\leq 120$ は普通の最短路問題です．
C. Palindromic Paths
距離 $2$ の $2$ マスを聞くことで，$2$ 択までは行けます．$x+y$ が偶数であるマスは確定，奇数のマスは全体フリップだけありうる感じになります．
あとは距離 $3$ の $2$ マスを $1$ 回聞きます．奇数マスの状況で返ってくる Yes, No が異なる質問を全探索すればよいです．最初の $3\times 3$ の部分で見つかります（$n=3$ で解けるならそうなるだろうという）．
D. Almost All
重心を根にとって，部分木を色 $A$ と色 $B$ に分けます．
このとき，どちらの色の頂点数も $n/3$ 以上であるようにできます．$1/3$ 重心分解で出てくる議論．
頂点数を $a,b$ として，片方の「深さ」が $1,2,\ldots,a$, もう片方の「深さ」が $a,2a,\ldots,ab$ となるようにすればよいです．
E. Expected Value Again
長さ $i$ の border があるという 0/1 値を $x_i$ として，求めるのは $(x_1+\cdots+x_{N-1})^2$ の期待値です．$x_i^2$ や $x_ix_j$ の期待値に分解します．これで，$O(\mathrm{poly}(N))$ 程度の解が得られます．
$i,j$ は border 長から period に置き換えておくと扱いやすいと思います．
これを愚直なループで実装すると，$i,j$ について $\mathrm{pow}(K,\max(i+j-N,\gcd(i,j)))$ を足すという形になります（文字列の periodicity lemma）．
まずは $\max(i+j-N,\gcd(i,j))$ の代わりに，
– $i+j<N$ ならば $\gcd(i,j)$
– $N\leq i+j$ ならば $i+j-N$
だとして計算しておきます．そのあと，これでは間違っている場合を修正します．
修正すべき $(i,j)$ は，$j$ と $g=\gcd(i,j)$ の組 $(j,g)$ ごとに高々ひとつで，全部で $O(N\log N)$ 通りしかありません．これで十分高速に計算可能です．
F. Beauty of a Permutation
permutation tree を考えて dp します．
– $4$ つ以上の子を集めて prime node を作る．beauty は子の beauty の和に $+1$ したもの．
– $2$ つ以上の子を集めて linear node を作る．beauty は子の beauty の和に $+k(k-1)/2$ したもの．
という遷移をします．はじめはこれで $O(N^7/w)$ という dp になって，（たぶんわずかに）TLE でした．
dp では，(頂点数，子の個数, 子の beauty sum) に対する bool 値を持っていたのですが，これを減らします．
長さ $1$ の区間のスコアを $0$ として扱うことにします．すると，$(n,k,b)$ が true ならば $(n+1,k+1,b)$ も true となります．
$(i,b)$ に対して，$(k+i,k,b)$ が true となる最小の $k$ を $\mathrm{dp}[i][b]$ とすることで，dp の持ち方を変えます．
これで $O(N^6)$ 解法になり，ループ範囲などをちゃんと切り詰めると十分高速になりました．
