A. NEKO’s Maze Game
縦や斜めに “##” が並ぶ場所の個数を数えて，その個数を差分更新します．
B. Aroma’s Search
入力の点の座標は $2$ 倍以上に増えていくので，$x_s+t$ 以下などの制限のもとで $60$ 個程度までしか見ないでよいです．
また座標は単調増加です．つまり $x_1\leq x_2\leq \cdots$ および $y_1\leq y_2\leq \cdots$ が成り立ちます．よって，$L$ 番目の点と $R$ 番目の点を訪れる解があるならば，その間の点もすべて訪れることが可能です．
$L,R$ を全探索して，$s\to L\to R$, $s\to R\to L$ が可能であるかを確認します．
C. Xenon’s Attack on the Gangs
mex として可能な値が $k$ であるとします．このとき値 $0,1,2,\ldots,k-1$ は同じパス上に並びます．
さらに少し考えると，このパスに $0,1,2,\ldots$ が隙間なく並んでおり，任意の $i$ について $0,1,2,\ldots,i$ は連結しているという形としてよいです．
$\mathrm{dp}[u][v]$ を，パス $u,v$ にこのように値を書いたときのスコアとして dp をします．
状態数 $N^2$ で，パスの両端を削るという遷移元しかないので計算量 $O(N^2)$ の dp が可能です．
D. Chaotic V.
木の頂点集合の重心を求める問題と見なすことができます．
根から見て各 subtree （素数）ごとの頂点の個数を求めておき，最も多くの頂点がある方向に進むことの反復によって重心が求められます．その移動の過程で答を差分更新できます．
E. Rin and The Unknown Flower
文字を ABC とします．
まずはコスト 1 で，BC, BA, CB, CA を聞きます．
何かがヒットした場合，その適当な極大部分文字列を拡張します．
基本的には，$i=2,3,4\ldots$ について，長さ $i$ の状態から次の文字の確定のために長さ $i+1$ の質問をするというのを $1$ 回ずつやります．
prefix 方向への拡張は，これができます．どの文字の手前も unknown ならば $2$ 択以下になのでひとつの質問でよいです．
suffix 方向への拡張では末尾が A のときだけは直後の文字が $3$ 択あります．ここでは A であるかをまず質問し，失敗した場合のみ B, C の判定をします．この「失敗」が起こった時点で末尾の文字は B または C ですが，これが起こった場合にはその次のフェーズでは B, C のどちらか（直後が unknown ならば確定）であることに注意します．
ここで最初の極大区間を選ぶときに末尾のものを選んでおけば，「失敗した場合には自動的に末尾まで確定する」という構造になるため，コストは $\left(\sum{3\leq i\leq j}\frac{1}{i^2}\right)+\frac{1}{j^2}& の形になって，これで上手くいっています．
次に，最初の $4$ つの質問が全部完全に外れだった場合です．
このとき，そもそも候補文字列の種類がまあまあ少なくて，
- AAAAAAAA
- AAAABBBB
- AAAACCCC
- BBBBBBBB
- CCCCCCCC
等のタイプしかないことが分かります（文字種が 1, 2 のどちらか）．
AAA を質問し，ヒットした場合は最初の $3$ つのどれか（文字境界位置も分かっている）ので簡単．
外れた場合には
- BBBBBBBB
- CCCCCCCC
- ABBBBBBB
- ACCCCCCC
- AABBBBBB
- AACCCCCC
のどれかとなりますが，B や C をたくさん並べるパターンなどを使って絞り込めます．
F. Nora’s Toy Boxes
弱連結成分分解して，連結成分ごとに解きます（最後にマージするのは簡単）．以下弱連結を仮定します．$2$ 点以下だと自明なので省略．
このとき，自身以外に約数を持たない要素を消すことは不可能です．このような要素の集合を $L$ として，自身以外に約数を持つ要素の集合を $R$ とします．$R$ の要素は $L$ 内に約数を持ちます．$L$ の要素が消えることはないので，問題文中の操作について $i$ は常に $L$ 内からとるとしてよいです．
各 $R$ の要素 $x$ について，$R$ の約数であるような $L$ の要素全体を $\mathrm{div}(x)$ とします．
$R$ の任意の要素について，それ $1$ 要素だけの状態にできます．これは操作を逆順に考えると簡潔です．
- 【逆操作】：$R$ の要素がいくつか生きている状態からスタートする．$i\in R$ が生きていて $j\in R$ が消えているとき，$\mathrm{div}(i)\cap \mathrm{div}(j)\neq \emptyset$ ならば $j$ を復活させることができる．
ここから，ある終状態が実現可能かの判定を，復活可能なものがある限り復活させるという貪欲法で判定できることを意味します．終状態としてある $1$ 要素の状態と目標として，これが実現可能かどうかを確かめましょう．実現不可能だとすると，$R$ の真部分集合から復活が進まなくなります．このとき，その集合とその約数である $L$ の要素全体で弱連結成分が作れてしまうので，弱連結の仮定に矛盾します．
よって答の操作回数は弱連結成分ごとに $|R|-1$ です．
操作仮定の数え上げもこの考察から簡単です．
$1$ 要素の状態からはじめて，生きている要素に対する $f(x)$ の和集合を保持する dp をすればよいです．
現在の要素数とこの和集合を保持し，和集合を変えない遷移・和集合を変える遷移それぞれを考えるようにすればよいです．
計算量について，$2^|L|$ という指数要素がありますが，$L$ の要素は $30$ 以下であることと $L$ の要素内に整除関係がないことから $|L|\lgeq 15$ が分かります．
