- https://codeforces.com/contest/923
- https://codeforces.com/contest/947 (div1)
- https://codeforces.com/contest/948 (div2)
A. Primal Sport
$X_i$ としてありうるもの全体を $i=2,1,0$ の順に求めます．$i=2$ は入力の $1$ 元集合で，そこから何らかの計算 $2$ 回です．ある数から $1$ 手遡るときは，素数の約数をひとつ選び，適当な区間全体に遷移するという形になります．
B. Producing Snow
現在保持している雪全体を適当な形で保持してシミュレーションします．ある日に溶ける量は，保持している雪の個数を基本として，そこからちょうどその日に消滅するものの分を補正すれば求まります．
保持している雪全体への定数加算と最小値取り出しをしたくなります．最小値取り出しは prique を使い，定数加算は代わりに第 $0$ 日に追加された場合の量を保持することで代用しています．
C. Perfect Security
先頭から貪欲に決めていけばよいです．集合 $S$ を管理し，「$x\in S$ の中で $x\oplus a$ が最小となるものを見つけて削除する」を繰り返せばよいということになります．これは Binary Trie の基本的な実装です．
D. Picking Strings
まずクエリを無視します．
$B\to AC\to AAB\to AAAC\to C$ のように $B$ は $C$ に変換，$C$ は $B$ に変換可能です．よって入力の $B,C$ はすべて同一視してよいです．
$AB$ 文字列で $A\to BB$，$B\to AB$，$AAA\to empty$ という操作が許容されているという問題にできます．$AB \to AAB\to AAAB\to B$ より $B$ と $AB$ も互いに変換可能です．よって $AB$ を可能な限り $B$ に置き換えてしまってよいです．
結局，操作前も操作後も $B^x A^y$ の形の文字列であるとしてよいです．ここまでくれば，末尾に対する $AAA\to empty$ の回数や $A\to BB$ の回数を考えると $O(1)$ 時間で判定できます．
区間クエリに対応するには，区間を上述の可逆操作を使って $B^xA^y$ に変形すればよく，これはセグメント木で行えます．
E. Perpetual Subtraction
巨大な行列に関する行列累乗の問題と解釈できます．適当な固有値・固有ベクトルがあると解けるというタイプだと予想して固有値を求める実験をすると，$\frac{1}{n+1}$ の固有ベクトル $(x-1)^n$ が見つかります．よって $F(x)=G(x-1)$ となる $G$ を求めたあと係数ごとに $\frac{1}{(n+1)^M}$ して，逆変換で戻せばよいです．$F, G$ の変換は polynomial taylor shift で $O(N\log N)$ 時間です．
実験等にたよらずにこの変数変換を発見する方法についても考えます．
考えるべき変換は，積分を使って $f(t)\mapsto \frac{1}{x-1}\int_{1}^{x}f(t)dt$ と書けます．$y=f(t)$ がこの変換の固有値 $\lambda$ の固有ベクトルだとします．つまり $\frac{1}{x-1}\int_{1}^{x}f(t)dt = \lambda f(x)$ とします．両辺に $x-1$ をかけて微分すれば，微分方程式 $\lambda(y+(x-1)y’)=y$ が得られます．これは変数分離形で，$y = (x-1)^{(1-\lambda)/\lambda}$ が解になることが分かります．ここから固有値 $\lambda=\frac{1}{n+1}$ に対して $(x-1)^n$ が固有ベクトルになることが発見できます．
F. Public Service
$4$ 頂点以上で，どちらも star でないならば常に可能です．
次の性質を使いました．
- $G_1$ の葉 $a_1, b_1$ および $G_2$ の葉 $a_2, b_2$ について，$a_1,b_1$ の親は異なり，$a_2,b_2$ の親も異なるとする．このとき，$G_1-\{a_1,b_1\}$ と $G_2-\{a_2,b_2\}$ に対する解を $G_1$ と $G_2$ の解に延長できる．
実際，$(a_1,a_2)$, $(b_1,b_2)$ と対応付けるか $(a_1,b_2), (a_2,b_1)$ と対応付けるかの $2$ 通りのうち少なくとも一方はうまくいきます．
このような $a_i, b_j$ が選べて，削除後も star にならないとき，再帰的に解くことにします．すると，片方 （$G_1$ とします）は次のどちらかの形になります．
- 直径が $3$ で，直径上の頂点を $a,b,c,d$ としたときその他の頂点はすべて $c$ に隣接している．
- 直径が $4$ で，直径上の頂点を $a,b,c,d,e$ としたときその他の頂点はすべて $c$ に隣接している．
このとき，解は次のように構築できます．$G_2$ の直径を $v_1,v_2,v_3,\ldots$ をとります．
前者のパターンならば，$a,b,c,d$ が $v_2,v_4,v_1,v_3$ に対応するようにすればよいです．
後者のパターンならば，まず $G_2$ の直径が $4$ 以上ならば $a,b,c,d,e$ が $v_2,v_4,v_1,v_3,v_5$ に対応するようにします．$G_2$ の直径が $3$ ならば必要ならば reverse することで $w$ を $v_3$ の近傍とし，$a,b,c,d,e$ を $v_3,v_1,v_4,v_2,w$ に対応させます．
