A. Painting With Two Colors
青の位置は左右対称に置かなければいけません．
赤は $a<b$ ならば青で覆えるので無視できて，そうでなければ左右対称に置かなければいけません．
B. Add 0 or K
すべて $K+1$ の倍数になるようにすればよいです．$K$ と互いに素な素数 $p$ をとって $p$ の倍数を作ろうとしてもよいと思います．
C. Even Larger
長さ $4$ 以上の subarray は，長さ $2,3$ の場合に分割できるので，長さ $2,3$ の場合のみが重要です．
長さ $2$ の方の条件から，まず奇数インデックスを隣接要素以下にします．
あとは長さ $3$ の方の条件です．奇数インデックスにあるものだけを取り出して考えると，隣接 $2$ 項の和の上界があるという形になります．
例えば最初の $2$ 項の和が違反していたとき，$1$ 項目はいじらずに $2$ 項目だけを減らすとしてよいです．長さ $2$ の場合の前処理のおかげでこれで $2$ 項目が負になる心配もありません．あとは同様に貪欲に決めていけます．
D. Sliding Tree
直径を考えます．これが $1$ 以上増えることはないことが簡単に分かります．
$1$ 増やす操作があります．
直径の頂点列を $v_1,v_2,\ldots,v_d$ として，$v_i$ の次数が $3$ 以上であるとします．$a=v_{i+1},b=v_i$ として $c$ を直径上にない $v_i$ の近傍とすることで，元の直径よりひとつ長いパス $v_1,v_2,\ldots,v_{i-1},c,v_i,v_{i+1},\ldots,v_d$ が発生します．
E. Power Boxes
ある時点で座標 $i$ から throw したときの値を $a_i$ とすると，$a_i-a_{i+1}$ が $0$ または $1$ になるというのが重要性質です．
あとは，次のように後ろから決めていくことが可能です．
- $a_{i+1}=a_{i+2}+1$ となっている場合：throw $i$ によって $i$ 番目が確定する．
- $a_{i+1}=a_{i+2}$ となっている場合：
- $1\leq i-1$ ならば，throw $i-1$ により $i-1$ 番目が確定する．swap と組み合わせることで，$3$ 回の操作で $i-1, i$ 番目が確定する．
- $1=i$ ならば，swap 1, throw 2 とすることで最後のひとつも確定する．
最後の $1$ 手を除いて，$1$ 回あたり $2/3$ 個以上のペースで確定できることから制約の操作回数が達成できることが分かります．
F. Permutation Oddness
lowbit が $1$ で確定する場所のことを考えます．すると，列全体を「奇数」「偶数」に塗り分けることを考えることになります．
パターンとしては mod 2 で見て連長圧縮したときに，
- 偶奇偶奇偶奇…偶奇
- 奇偶奇偶奇偶…奇偶
- 偶奇偶奇偶奇…偶奇偶
- 奇偶奇偶奇偶…奇偶奇
などがあって，このパターンごとに答を求めることを考えます．
すると，次のような小問題を解いておけばよいです．
- $a,b$ が与えられる．各 $k, v$ について次を求めよ：
- $0$ が $a$ 個，$2$ が $b$ 個ある．これらを並べたあとで何か所で切って，空でない subarray $k$ 個に切り分ける．$0$ と $2$ が隣接する箇所が $v$ 個になるような方法を数えよ．
小問題の答から問題の答を出すのは，単純な $O(n^3)$ 時間のアルゴリズムでできます．
商問題は $O(n^2)$ で解けます．まず $k=1$ の場合を求めておき，あとは列を切る操作を $1$ 回ずつ行う形で dp を進めればよいです．$0$ と $2$ が隣接の個数を持っておけば同じ値同士の隣接の個数もわかるので，列を切る場所が同種か異種かで分類して計算できます．
