A. Shortest Increasing Path
$x<y$ なら $2$ 手でできます．$2\leq y$ かつ $y+2\leq x$ のとき $3$ 手でできます（$1, y, x-1$ とする）．
それ以外は不可能です．$y=1$ は初手を考えると不可能．$y\leq x\leq y+1$ を考える．偶数回行動だと $x<y$ となってしまうのでこのとき奇数回行動．$3$ 回以上行動する．すると，$2k,2k+1$ 回目の行動をペアにして考えることで $y+2\leq x$ が必要ということになってこの場合も不可能．
B. Multiple Construction
$N=10$ なら $[8,6,4,2,*,2,4,6,8]$ と $[9,7,5,3,*,*,3,5,7,9]$ を作って調整すると $[8,6,4,2,10,2,4,6,8,1,9,7,5,3,10,1,3,5,7,9]$ が得られる．という要領で全部作ることが可能です．
C. Rabbits
$i$ 番目のうさぎの右隣のうさぎまでの距離を見て
- $3$ 以上なら $i$ 番目のうさぎの右移動は禁止
- $2$ ならば「$i$ 番目のうさぎが右移動なら $i+1$ 番目のうさぎは左移動」
というような条件があります．twosat でそのまま解けます．dp でもよいです．
D. Game on Array
奇数のうち頻度が大きいものからとっていく貪欲法（なければなんでも）が最適である，ということを $\sum A_i$ に関する帰納法によって示します．
帰納法の仮定のもと，
- 奇数が存在しないとき：適当なものをとると，相手は同じものを真似してとることになって，結局半数ずつとることになる．何をとってもスコアは変わらない．
- 奇数があって，自分が偶数をとる戦略について：相手は真似をすることを考えると帰納法より先手は得をしない．
- 奇数があって，自分が頻度が最大でない奇数をとる戦略について：帰納法の仮定より損
であることなどが簡単にいえます．「$A_i$ がすべて偶数なら，両者にとって，自分が半分以上とれる戦略が存在する」というところから考えましたが，私は証明は帰納法でした（偶数は削除したゲームを考えればよい，というようなことを直接証明しようとしたけど失敗）．
E. Maximum OR Popcount
各 $k$ について，OR popcnt を $k$ 以上にするための最小コストを求めればよいです．
次を満たす最大の $k$ をとります：$2^k$ の位の初期値が $0$ であり，最終的には $1$ である．$k$ はすべて試して答を求めます．
$k$ を最大にとっているため，入力はすべて $2^k$ 未満であるとして考えてもよいです．またこのとき，$2^{0},\ldots,2^{k-1}$ の位についても $1$ を目指すことになります．そうでないならば，$2^k$ の位が繰り上がる直前で止めておいた方が良いということになるからです．
どの $A_i$ を使って $2^k$ の位を $1$ にするかですが，これは最大の $A_i$ を使えばよいことが簡単な exchange argument で分かります．結局 $k$ 桁目から上から順に，「現在の OR の $2^k$ の位が $0$ ならば $\pmod{2^k}$ で最大の $A_i$ で $1$ を作る」という操作を繰り返すのが最適になります．
F. Exchange Queries
アイテムを平面上の点 $(s_i,p_i)$ だと思います．
$[0,n)\times [0,n)$ に $n$ 個のアイテムがあるところで区切るというのが強連結成分分解の形になります．
アイテムは「ここでは区切られません」という情報です．だいたい次の形になります．
- 列 $A_0, \ldots, A_N$ があり，最初すべて $0$ である．（ここでは区切られないという情報の個数）
- アイテムの追加：$A_L, \ldots, A_R$ に $+1$．
- アイテムの削除：$A_L, \ldots, A_R$ に $-1$．
- 答の計算：$A_i=0$ であるような $i$ 全体を $0=i_0,i_1,\ldots,i_k=N$ とする．$\sum_j\binom{i_{j+1}-i_j}{2}$ を求めよ．
これは遅延セグメント木で処理します．有名なのは $A_i=0$ となる $i$ の数え上げで，「$A_i=0$」という条件を「$A_i = \min A$ かつ $\min A = 0$」に置き換えるというテクニックを使います．ここでも同じようにして，セグメント木の集約値として
- $\min A$
- $i=\min A$ となる $i$ の最小値・最大値，およびそのような $i$ を対象にした $\sum_j\binom{i_{j+1}-i_j}{2}$
を持たせればよいです．
G. Modular Tetration
まずは判定します．$a^k\equiv 1\pmod{m}$ となる最小の正整数 $k$ をとります（なければ $a$ は bad）．すると，$a$ の十分大きな tetration が $k$ の倍数になるという条件になります．よって，$\mathrm{rad}(k)\mid a$ というのが条件です．$\mathrm{rad}(k)$ と $m$ が互いに素でなければならないことも分かります．$\mathrm{rad}(k)$ の素因数としては，$\varphi(m)$ の素因数であるが $m$ の素因数ではないというものが候補になります．
このような素数を $q_1,q_2,\ldots$ とします．$\mathrm{rad}(k)=\prod_{i\in I}q_i$ となる $a$ の個数を数えたいです．包除原理を考えて，まずは $\mathrm{rad}(k)\mid \prod_{i\in I}q_i$ となる $a$ の個数を求めます．$Q=\prod_{i\in I}q_i$ とします．
$L$ を十分大きくとって，$\mathrm{pow}(a,Q^L)\equiv 1\pmod{m}$ という条件です．$m=\prod p_i^{e_i}$ として，中国剰余定理で数えます．$p_i$ が奇素数ならば $(\mathbb{Z}/p_i^{e_i}\mathbb{Z})^{\times}$ が巡回群であることを利用すると，$\mathrm{pow}(a,Q^L)\equiv 1\pmod{p_i^{e_i}}$ は $\pmod{p_i^{e_i}}$ で $\gcd(\varphi(p_i^{e_i}),Q^L)$ 個の解があります．$p_i=2$ に問題がありそうですが，このとき $Q$ は奇数で，$\mathrm{pow}(a,Q^L)\equiv 1\pmod{p_i^{e_i}}$ の解はひとつであり，やはり $\gcd(\varphi(p_i^{e_i}),Q^L)$ 個です．
よって，$\mathrm{pow}(a,Q^L)\equiv 1\pmod{m}$ の解は，$\prod_i\gcd(p_i^{e_i},Q^L) = \gcd(\phi(m),Q^L)$ 個です（$L$ が十分大きいことを使いました）．
結局，解は次のように計算できます．
- 集合 $I$ に対して$a_I=\gcd(\varphi(m),(\prod_{i\in I}q_i)^L)$ により定まる $a$ を考える．
- これを部分集合に関するメビウス変換したものを $b_I$ とする．
- $\displaystyle \sum_{I}\frac{b_I}{m\cdot \prod_{i\in I} q_i}$ が答え
$Q_i=\gcd(m,q_i^L)$ とすれば，$a_I=\prod_{i\in I}Q_i$ です．よって $b_I = \prod_{i\in I}(Q_i-1)$ です．答は
$\displaystyle \frac{1}{m}\sum_{I} \prod_{i\in I} \frac{(Q_i-1)}{q_i}$ ですが，これは $\displaystyle \frac{1}{m}\prod_{i\in I} \left(1+\frac{Q_i-1}{q_i}\right)$ です．
H. Maxflow GCD Coloring
実は答は $2$ 以下です．$1$ 色であるかを判定し，そうでなければ $2$ 色で構築するというのが解法となります．
これが予想できれば AC するのは簡単です．
- $1$ 色であるかの判定：全点対で最大流を解く（Gomory-Hu Tree のようなものを持ち出しても良い）．
- $2$ 色の場合の構築：条件は $\mathbb{F}_2$ 上の連立方程式で書ける．具体的には $v$ の次数が偶数ならば近傍の総和が $0$，奇数ならば近傍と自身の総和が $1$ とすればよい．
これで AC できましたが，まだ $2$ 色で可能であることの証明はできていません．
解説を見るとすごい方法が．次のようにします．
- 次数奇数の点が存在しないならば，すべての点を色 $0$ とすればよい．
- 次数奇数の点 $v$ があるとする．近傍 $w_1,w_2,\ldots,w_k$ とするとき，頂点 $v$ を削除したあとすべてのペア $w_iw_j$ の間に辺をひとつ追加する．これで再帰的に解く．そのあと，近傍のうちで偶数個ある方の色に $v$ の色を決める．
- 後者の操作で $v$ が条件を満たすことはよいです．$w_i$ のうち偶数個あった方の色が条件を満たすことが分かりにくいですが，この点からは同色の追加辺奇数個が，同色の $v$ への辺ひとつに置き換わるので大丈夫です．
連立方程式を解くと思って，$v$ の条件で掃き出すという操作に対応しています．
もう少しグラフ線形代数の有名事実から証明できるのではないかと思うのですが，分かりませんでした．（HELP）
I2. Longest Increasing Path (Hard Version)
おおよそ次のようにします．
- 点 $a_1,a_2,\ldots,a_n$ を用意する（区間 $[a_i,a_i+d)$ を何度も使う想定）．
- 添字組の列 $(i_1,j_1),(i_2,j_2),\ldots$ をいい感じにとる．
- $(i,j)$ での往復操作をする：$a_i+d-1,a_j+0,a_i+d-2,a_j+1,a_i+d-3,a_j+2,\ldots,a_i,a_j+d-1$．
- $2$ 個組の間をいい感じに移動する．
これをいい感じに調整すると解が得られます．
添字組を $\binom{n}{2}$ 組とれるとすると，
- 列の長さが $N$ 以上：だいたい $\binom{n}{2}\cdot 2d\geq N$
- 種類数が $M$ 以下：だいたい $nd\leq M$
という感じにパラメータ調整します．結論としては，$W$ を大きくとって $a_i = W\cdot 2^i$ で大丈夫でした．あとは間の移動をいい感じに作れば大丈夫です．
