A. Another Puzzle from Papyrus
reorder は $0$ 回または $1$ 回としてよいです．それぞれ解きます．
どう並べようが減算回数は sum の差なので，$a_i\geq b_i$ になっているか（並べられるか）だけが問題です．
reorder 版は，$A, B$ をソートしてチェックします．
B. Crimson Triples
素因数ごとに条件を考えると，$b$ の割れる回数が最小ということになります．（私は $a,b,c$ の大小順 $6$ 通りチェックしました．）
結局 $a, c$ が $b$ の倍数という条件です．$b$ についてループして計算します．
C. Village Guilds
同じ guild に対して，LCA 部分での操作だけを数えることにします．
LCA 側から見ると，$2$ つ以上の部分木方向にその距離の点があればよいという感じになります．
子の高さのリストをソートして何かを足すというタイプの計算をすればよいです．
D. Storming Arasaka
コンテスト中はサンプルが合うように実装しただけ，ちゃんとした証明は少し難しい.構築させた方が良かったのでは？
素数は単独で $1$ layer 使います．あとは，$N$ の重複度を込めて数えた素因数の個数を $k$ とすると，長さ $k$ の整除関係があって，そこから余分に $k-1$ layer 必要だと分かります．
構築は，ちょうど $k$ 個の素数の積であるようなものを適切に並べられることが帰納法で示せるはず．
雰囲気証明：
ひとつの $p$ に注目し，「$p$ の倍数以外全体」→「$p$ の倍数全体」と並べることを考えます．
「以外全体」の部分を帰納法の仮定で処理して，接続部分は $k\geq 2$ から他の素因数でつなげばよいはず．
E. Cake Trial
読解ややこしい．
TF 文字列が確定している場合，区間の選び方の最適化は，左から順に dp で行えます．
区間を選ぶのは，文字種が $3$ の文字列：000011112222 の形を作ることと思います．
- 最後に置いた文字が 0
- 最後に置いた文字が 1
- 最後に置いた文字が 2
の場合に，その時点まででの不一致を最小化した場合の値．という $3$ つの値をもって dp すればよいです．
この dp を「dp1」と呼びましょう．
今度はこれを，文字を決める側目線で，この dp1 状態がどのくらい都合が良くできるかを考えます．
まず考えられるのは，
- dp2[a][b][c] := 「dp1=(a,b,c) となることがありうるように TF 列を決められるか」の bool
という dp です．定義がややこしいですが．これを
- dp[a][b] := 「dp1=(a,b,c) となることがありうるように TF 列を決められるような c の max」
とします．あとは dp1 の計算方法を確認しながら dp を計算していきます．
F. Infinite Work
まず読解の時系列とかがめちゃくちゃ難しいです．親切に図がついてるんですが，この最後の図のあとに，firing フェーズがあって，誰も firing せず，day 3 (= 2 days after) を迎えるという順です．
結局，こうなります．
- $M$ 個の頂点を選ぶ（direct firing 対象）．先祖子孫関係にない，かつ，深い点をすべて被覆する感じにとる．
- それぞれ，$2 ^ h – 1$ の形の部分木サイズに取り換える（ただし $0\leq h < n$）．
- $k$ 頂点になるようにしてください．さらに $M$ を最小にとってください．
読解に苦労しすぎて，読解成功したころには $M$ の最小化について忘れていて，苦戦．
まず，$M$ を固定して考えます．木の選び方は，二分木の数え上げで，カタラン数登場です．このときの内部頂点の個数も $M-1$ という定数になります．
あとは，$2^k-1$ を振り分けるところが問題です．
言い換えれば，$f(x) = \sum x ^ {2 ^ h – 1}$ として，
$$[x ^ {k – M + 1} ] f(x)^M \neq 0$$
が成り立つように最小 $M$ をとり，そのときの係数を求めるということになります．
さらに言い換えれば，$g(x) = \sum x ^ {2 ^ h}$ として，
$$[x ^ {k + 1} ] g(x)^M \neq 0$$
が成り立つように最小 $M$ をとり，そのときの係数を求めるということになります．
これは，$k+1$ を $2^0,2^1,\ldots,2^{n-1}$ の最小個数に分割する方法を数えよと言っているだけです．
同じ $2^i$ は $i < n-1$ ならば $1$ 回以下しか使わないことが確定します．（$2$ 回使うならまとめられる）
すると $\bmod 2^{n-1}$ で見て，それぞれ使う回数が確定します．
全部の使う回数が確定するので，$M$ も簡単に決まるし，振り分け方は適当な多項係数です．
私の提出はこの辺に気づかず，$g(x)$ じゃなくて $f(x)$ のままやってるし，多項式の必要な幅が $2^n\cdot n$ 程度でおさえられるだろうという観察に基づいて計算量を落として何とか，という感じでした．かなり下手．
