A. Lever
$2$ 種類目の操作は $1$ 種類目の操作が行える回数に影響しないです．単に $1$ 種類目の操作が行える回数を数えます．
B. Alternating Series
- 奇数のときの解： $-1,3,-1,3,-1,3,-1$
- 偶数のときの解：$-1,3,-1,3,-1,3,-1,2$
のようになります．いずれも先頭から見てこの解よりも絶対値が小さくしようとすると，その前後の項からすぐに矛盾がいえます．
C. Make it Equal
$x\to y$ と変換可能ならば $y\to x$ とも変換可能です．変換可能なものを同一視できるようにしてから一致を検出すればよいです．
例えば $k=10$ のとき，
- $0,10,20,30,40,\ldots$
- $1,11,21,31,41,\ldots$, $9,19,29,39,49,\ldots$
- $2,12,22,32,42,\ldots$, $8,18,28,38,48,\ldots$
- $3,13,23,33,43,\ldots$, $7,17,27,37,47,\ldots$
- $4,14,24,34,44,\ldots$, $6,16,26,36,46,\ldots$
- $5,15,25,35,45,\ldots$
に分類できます．
D. Arboris Contractio
かなり難しいと思った．
$n\geq 3$ として，star を作ります．最終的に star の中心になる点 $v$ を固定して考えます．
$X$ を「$v$ との距離が $2$ 以上であるような葉の個数」という量だとします．$X$ が操作によって高々 $1$ しか減らないことをチェックします．操作するパス $st$ の長さは $2$ 以上だとしてよいです．
$v$ との隣接関係（距離 $1$ 以下であるかどうか）や次数が変化する可能性がある点は，$st$ パス上の点だけです．$st$ パス上の点で葉である可能性があるのは $s,t$ だけなので，$s,t$ がともに $v$ と距離 $2$ 以上の葉であるときだけが問題です．特にこのとき $v\neq s$ です．$t$ は隣接する点が $s$ のみであるような葉へと変わりますが，これは操作後も $v$ との距離が $2$ 以上であることが分かります．これで $X$ が高々 $1$ 以下しか減らないことが確認できました．
一方で，$s=v$ として，$v$ との距離が $2$ 以上であるような葉を $t$ として操作することで，$X$ は必ず $1$ 減少させることができます．
よって star の中心としたい $v$ を決めたときの最小操作回数が $X$ であることが示せました．
E. Adjacent XOR
$a_i$ は高々 $1$ 回しか変化しません．$i$ 番目の項を操作しない，$i+1$ 番目の項が変化する前に操作する，$i+1$ 番目の項が変化した後に操作する，という場合分けによって次の必要条件が得られます：$b_i\in \{a_i,a_i\oplus a_{i+1}, a_i\oplus b_{i+1}\}$
この必要条件のもと条件を満たす操作順は存在します．
操作順の存在は「$i, i+1$ 番目の操作のどちらを先にやってほしい」という要望がいくつかあるのでそれらをすべて満たすようにせよ，ということです．これは $i\to i+1$ または $i+1\to i$ に辺を張ったときに topological sort 可能かということです．この有向グラフにはもちろんサイクルがないので topological sort 可能です．
F. Unjust Binary Life
まず $f(x,y)$ を求めます．これは次の $2$ 通りの min ということになります．
- $a_1=\cdots=a_x=0$ かつ $b_1=\cdots=b_y=0$ となるようにするコスト．
- $a_1=\cdots=a_x=1$ かつ $b_1=\cdots=b_y=1$ となるようにするコスト．
結局，求める総和は次のように書けます：$\sum_{x,y}\min(f_0(x)+g_0(y),f_1(x)+g_1(y))$．
$y$ を固定したときのことを考えると，$f_0(x)-f_1(x)$ がいくつ以下のときはこれ，いくつ以上のときはこれを足してくださいという形になっています．$x$ を $f_0(x)-f_1(x)$ でソートして，適当な累積和テーブルを用意しておけばまとめて計算できます．
G. Wafu!
- $\{m\}$ に対して空になるまで操作をしたときの操作回数
- $\{m\}$ に対して空になるまで操作をしたときに ANS に書ける値
などを各 $m$ について求めておきます．$\dp[m]=1+\dp[1]+\cdots+\dp[m-1]$ （あるいは $m\times \dp[1]\times\cdots\times \dp[m-1]$）のような漸化式で計算できます．
操作回数は指数的に増えていくことが分かります．よって $m$ は非常に小さい範囲だけ計算しておけば十分です．
あとはこれを利用してシミュレーションします．$m$ が消しきれないとなったときには，$1,2,3,\ldots$ と消せるところまで操作したあと，消せない最初の値だけを残します．このとき残る値は十分小さいため，愚直なシミュレーションが十分高速になります（$O(n+\log^2k)$ 時間などで解ける）．
H. Sea, You & copriMe
まず，ペアをひとつ見つけることを考えます．
各値は radical に置き換えて（$\prod p_i^{e_i}$ を $\prod p_i$ に置き換えて）おいてもよいです．$i=0,1,2,\ldots$ 順に見て，各 $i$ について「$j<i$ かつ $\gcd(a_j,a_i)=1$ となる $j$ の個数」が計算できます．これは約数列挙と包除原理を使えばよいです．この個数が正となる最初の $i$ が見つかったら，$j$ は愚直なループで発見できます．
これでペアを（存在するならば）ひとつ見つけることができました．
計算量は，約数の個数の和で評価できますが，同じ $a_i$ の値は通常 $1$ 回まで（$1$ のみ $2$ 回まで）しか見る必要がないことから，その平均化である $O(m\log m)$ 時間でおさえられます．
ペアを $2$ つ見つけるには次のようにすればよいです：
- 列をランダムシャッフルする．ペア $(a,b)$ を $a>b$ かつ $a$ が最小となるようにとる．ペア $(c,d)$ を $c<d$ かつ $c$ が最大となるようにとる．$a<c$ ならば成功．
$a$ が最小，$c$ が最大であるようなペアは上で述べた方法で発見できます．
この乱択アルゴリズムの成功確率を評価します．$2$ つのペアが列の中にあってそれらをランダムシャッフルしたときに，それが左右に分離される確率を考えればよいです．この確率は $8/24=1/3$ であることが分かるので，この乱択を $k$ 回反復すれば，失敗確率は $(2/3)^k$ 以下となります．
私の提出では $k=20$ として，失敗確率を $0.03\%$ 程度になっています．
追記1．上の提出はハックされていましたが，マルチテストケースであることを考慮すると失敗確率が $0.03\%$ あるというのは大きすぎるということでした．
追記．$1$ 組を求めることが可能なら，あとは次のように解けます．
まず $1$ 組求めて $(a,b)$ とします．次に $(a,b),(c,d)$ の形の解を探します（$2$ 個消した後同じように解くだけ）．これがないならば，あとは $(a,c),(b,d)$ の形の解を探します（これは各要素が $a,b$ と組に出来るかを調べるだけで $O(N)$ 時間）．これは一般グラフのマッチングの理論において，交互路によるマッチングの増加を試みるのとも同じです．
