A. Photo of The Sky
$a$ がソートされているとします．これらを $2$ 色で塗り分ける（$x$ 座標として使うものと $y$ 座標として使うものに分ける）と考えます．
$a_1,a_{2n}$ を異なる色にする場合，$(a_1,\ldots,a_n),(a_{n+1},\ldots,a_{2n})$ と分割するのが最適解のひとつです．これは各色ごとに最大値と最小値の差を最小化できているためです．
$a_1,a_{2n}$ を同じ色にする場合，残り $2n-2$ 個から $n$ 個を選ぶ問題になり，これは連続する $n$ 個というパターンを全探索すればよいです．
B. Chemical table
セル $(i,j)$ を行番号 $i$ と列番号 $j$ を結ぶ辺だと見なすテクニックです．
二部グラフにおいて長さ $3$ のパスがあるときにこれをサイクルにできます．すると可能な限り辺を追加したとき，任意の $2$ 点の距離は $2$ 以下になり，二部グラフであることと合わせて任意の連結成分は完全二部グラフになることが分かります．すべての辺を作るためには連結になるまで辺を足すのが最適です．
C. Hills
まずは家を建てる丘を決めたときの戦略を考えます．これは簡単で，予定地の高さは変更せず，その隣接する場所の高さは必要最小限減らすことになります．
家を建てる丘を左から順に決めていくことを考えて dp 可能です．各場所のコストを計算するには，直前の数か所について家を建てたかだけを持てばよい（その正確なインデックスは不要）です．これと家の合計個数の組として $i$ ごとに $O(N)$ 状態を持って順に更新していけばよいです．
D. AB-Strings
連長圧縮すると，それぞれの文字列は ABABAB の形としてよいです．一度 AAAAA のようになっている部分を切る操作を含む操作列は，そのような最後の操作以降を適切に変更すれば，連長部分を切らない操作列にして損しないようにできるからです．
すると状態として，各文字列の先頭の文字および長さだけから最小操作回数が決まることが分かります．
あとは小さい場合を愚直実装してしまい正しい式を予想するのが簡単でしょう（こういうのは予想できてさえしまえばたいてい帰納法で証明できる）．コストが正しく計算できるようになったら，操作 $1$ 回で必要コストが $1$ 減るような操作を適当に探索すればよいです．
E. Cycle sort
まず $a$ が順列だとして考えます．サイクル分解します．
- 長さ $2$ 以上のサイクルに含まれる要素は，必ず一回以上操作する（操作するインデックス集合に含める）必要があります．
- ちょうど一回しか操作しない要素しかないサイクルは，そのサイクルだけで操作回数 $1$ を消費することになります．
- サイクル $C_1,C_2,\ldots,C_n$ に対して，それぞれのサイクルから $2$ 回操作してもよい要素をひとつずつ選べば，$2$ 回の操作でこれらすべてをソートできます．
操作する要素数の合計が $s$ 以下になるという条件から，$2$ 回操作してもよい要素の個数上限が決まり，そこからなるべく多くのサイクルをまとめて $2$ 回操作でソートする，というのが大まかな流れになります．
あとは，入力が順列ではないという要素に対処します．ソート後の列を $b_1,\ldots,b_n$ とします．$a_i=b_i$ であるような $i$ は操作不要なので無視します．各 $a_i$ を $b$ のどの位置に持っていくかに（順列ではないことより）任意性があり，これをサイクルの個数が最小になるように選びたいです．
インデックス $i$ を有向辺 $a_i\to b_i$ と思ったとき，インデックス $i$ の移動先は同じ連結成分内の辺でなくてはいけません．一方連結成分は eulerian なのでサイクルをとることで，移動先が cyclic shift の関係になるように連結成分内の移動先をすべて決めることができます．
F. Passports
$P=2$ とします．基本的に「パスポート1」と「パスポート2」は独立です．そこで，各旅行の集合 $s$ に対して，$s$ をひとつのパスポートで処理できるかを考えることにします．
これは，trip の列を visa を申請する順に作っていく dp で計算できます．
簡単のため trip 1, 2, 3, … の順に visa 申請するとします（出発日 $s_1, s_2, \ldots$ の順序は仮定していません）．列の後ろに trip を追加するときには，「これまで選んだ trip の旅行期間に手元にパスポートが存在」「申請日は（別パスポートのものも含めて）旅行していない」「その trip の出発日に申請が間に合っている」という必要条件があります．逆にこの必要条件を満たすように trip を追加していけばその trip 集合は valid になっていることが確認できます．
申請日は，可能ならばなるべく早い日の方がよいです．よって dp で持つ値は申請日（またはパスポートが返却される日）とします．「なるべく早い申請日」については，直前の申請が終わった時点，または何らかの trip からの帰宅直後が候補となります．
これで $O(2^N\times \mathrm{polynomial}(N))$ 程度にはなるでしょう．
ある集合に trip を追加するとき，$t_i$ の昇順に trip を試すことで，可能な最も早い申請日は昇順になって，全体で $O(2^N\times N)$ 時間になります．
ただしそれでも定数倍がなかなか厳しくて，私は定数倍がなるべく良くなるよう実装の工夫が求められました．
