A. Colour the Flag
完成形の候補は $2$ 通りしかなくて，それらを試せばよいです．
B. Histogram Ugliness
$a_i<a_{i+1}>a{i+2}$ となっている部分だけを削るのが最適です．
証明は帰納法で示すのが簡単だと思います．
C. Little Alawn’s Puzzle
$n$ 頂点からなるグラフを考え，$i$ 番目の列を上の数と下の数を結ぶ辺と見なします．
パズルの解とは，各辺の向きづけであって，すべての頂点の入次数・出次数が $1$ であるものということになります．
連結成分ごとにちょうど $2$ つの解があります．
D. Lost Tree
$1$ 回の質問である点の近傍はすべて手に入ることに注意します．
まず，適当な点をクエリすることで，木を深さ偶数・奇数の点に分割します．
分割された $2$ つの頂点集合のうち小さい方について質問します．これですべての辺が見つかります．
質問回数は $1+\left\lfloor \frac{n-1}{2}\right\rfloor$ 以下です．
E. Lost Array
$\mathbb{F}_2$ で考えます．質問を，長さ $n$ の行ベクトル（$1$ である成分が $k$ 個）と考えます．
質問で $\sum a_i$ が特定できているかというのは，行ベクトル $(1,1,1,\ldots)$ が質問で生成できているかということです．よって，質問の総和で $(1,1,1,\ldots)$ を作る問題ということになります．
言い換えれば，
- 要素ごとの質問回数の列 $(b_1,b_2,\ldots,b_n)$ を上手く決める．
- $b_i$ はすべて奇数．
- 「相異なる要素 $k$ 個」に分割可能．
というようにしたいです．$b=(1,1,1,\ldots)$ からはじめて，最小要素に $+2$ することを繰り返して当たり待ちすればよいです．
F2. Falling Sand (Hard Version)
まず，ある砂が落ちるとこの砂が落ちるという連鎖関係で有向グラフを作ります．
いくつかの始点を選び，各列について下から $a_i$ 番目の砂を通るようにするという問題になります．
落とす砂は，各列のうち一番上のものだけとしてよいです．
ある目標の砂を落とせている条件は，ある $l,r$ があって「$[l,r]$ 番目の列の砂からひとつ以上落とす」という形になります．
このような $l,r$ を DAG 上の DP で求めれば，あとは適当なグラフを忘れて区間の問題になります．
G. A New Beginning
経路を固定したときのコスト最小化ですが，これは，$x+y=x_i+y_i$ であるような $(x,y)$ を通ったときにマンハッタン距離のコストがかかると思うことができます．
$x_i+y_i$ について昇順に処理して，通る場所に対する最小コストは何かという関数を管理することを考えると，slope trick の基本操作で答を求めることができます．
H. Lost Nodes
インタラクティブ形式ですが，最適解を木DPで求めることができればインタラクティブ形式への対応は簡単です．
$f$ が与えられることから，根付き木に対する木DPを考えます．$\dp[v]$ としては，以下の値を定義します．
- パスの端点が $v$ 内にあるならばその端点を，そうでなければ $v$ からパス $ab$ に最も近い点を求める．そのために必要な最小質問回数．
$v$ の子が $c_0,c_1,\ldots,c_{k-1}$ であるとき，$\dp[c]$ が降順になるようにソートしたうえで $\dp[c]=\max (dp[c_i]+i)$ となることが分かります．
根での答を求めるには，やはり $\dp[c]$ が降順になるようにソートしたうえで，$2$ 個のパス端点が見つかるまで処理することを考えれば，$\max (\dp[c_0]+\dp[c_i]+(i-1))$ のようになることが分かります．
あとは，これを全方位DPですべての根に対して求めることにします．
単純な子の dp 値をソートするという操作が含まれるため，モノイド演算にしにくくて，よく知られている全方位DPの抽象化には当てはめにくいと思いますが，あまり問題は起きないです．まずは bottom up な木DPを行った後，top down に辺の親側部分木の値を求めていきます．このフェーズでは各頂点で次のような計算をすればよいです．
列 $a_0,a_1,\ldots,a_d$ がある（降順ソートしておく）．「ひとつ削除したあとでソートしてインデックスをつけなおし $\max(a_i+i)$ を求める」ことをすべての削除対象について行ってください．
