A. Omkar and Password
種類数 $2$ 以上ならば長さを $1$ にできます．max とそうでないものの隣接があるため，そこに操作をすることで種類数 $2$ 以上を維持できます．
B. Omkar and Infinity Clock
$1$ 回操作すると最小値が $0$ になり，その状態からは $2$ 回操作するたびに元に戻ります．
C. Omkar and Waterslide
$2\leq i$ に対して $a_i$ を左端とする操作が少なくとも $\max(a_i-a_{i-1})$ 回必要です．
後ろの $i$ から順に，suffix 全体に操作することを繰り返せばこの下界を達成できます．
D. Omkar and Bed Wars
同じ文字が $3$ 連続で続かないというのが条件になります．適当な dp で最適化できます．
E. Omkar and Duck
$(i,j)$ には $0$ または $2^{i+j}$ を置きます．$i+j$ が一定のところに対してこの $2$ 種を交互に置いておくと，経路が復元できるようになります．
F. Omkar and Landslide
代わりに $a_i = h_i – i$ を考えるのが簡単だと思います．
入力は $a_j\leq a_{j+1}$ を満たします．起こることは，$a_j+1\leq a_{j+1}$ のときに $a_{j+1}$ から $a_j$ に $1$ うつすというものです．
操作によって次が維持されることが証明できます．
- $i<j$ ならば $a_i\leq a_j+1$ が成り立つ
$a$ に対して操作を行った結果を $b$ と書くことにして，$i<j$ に対して $b_i\leq b_j+1$ を示します．$a_i=x$ とします．
- $a_{i+1},a_{i+2},\ldots$ はすべて $x-1$ 以上である．このことから $x-1\leq b_j$ が分かる．よって $b_i\leq x$ ならば $b_i\leq b_j+1$ である．
- $x<b_i$ だとする．このとき $x+1\leq a_{i+1}$ かつ $b_i=x+1$ である．仮定より $a_{i+1},a_{i+2},\ldots$ はすべて $a_{i+1}-1$ 以上であるから $x$ 以上．よってこの場合も $x\leq b_j$ がいえる．
示せました．
あとは，$a$ の総和が不変であること，終状態において $a$ は広義単調減少であることから終状態が一意に定まります．
G. Omkar and Pies
$S, T$ から $n$ 個分のスワップを行った結果を $S[n], T[n]$ とすれば，$L<R$ を上手く選んで $dist(S[L],T[R])$ を最小化する問題です（dist は文字が異なるインデックスの個数）．
$R$ を止めて処理することを考えます．各 $x$ に対して，$S[i]$ との距離の $0\leq i\leq L$ での最小値が更新されるような $L$ は $k$ 個程度しかないので，これらを計算しておけばよいです．
H. ZS Shuffles Cards
素直な dp を考えると，状態は「$n$ 枚のカード，$n’$ 枚の無意味なカード，$m$ 枚の joker」のようになります．無意味なカードというのは既に $S$ に追加されているカードです．この場合の値を $dp[n]$ とします．
無意味なカードなしの $n+m$ 枚でゲームをやるときに比べて，期待値は単に $(n+n’+m)/(n+m)$ 倍されます．よって無意味なカードは立式においてほとんど無視できます．
あとは適切に立式すれば，累積和により高速化できることが分かります．
I. Kevin and Grid
グリッドの各マスの中心を頂点として平面グラフを作ります．
グリッドを 2 色 A, B に塗り分けたとします．Euler の公式から，次の式が得られます．
$$V_A-E_A+F_A=C_A=\text{good}_A+\text{bad_A}.$$
$V, E, F, C$ は頂点数，辺数，面数，連結成分数です．good, bad は問題文で定義されているやつです．
ここで，bad な連結成分の外周はすべてある色 B の面であるということがいえます．逆に色 B の面に対して，それが $2\times 2$ の正方形である場合を除いて，内側に bad な色 A の連結成分が対応します．したがって $2\times 2$ 正方形の個数を $S_A$ として，
$$\text{bad}_A = F_B-S_B$$
が分かります．よって
$$\text{score}_A=V_A-E_A+F_A+F_B-S_B$$
が分かります．色を入れ替えてできる式との差をとれば，スコアの差が $V, E, S$ から計算できることが分かります．V, E, S は畳み込みを利用して計算できます．
