A. Hongcow Builds A Nation
最終的には，すべての連結成分が特殊頂点をちょうどひとつ含むクリークになります．
現時点での成分があるとき，特殊頂点を含まない成分を何らかの成分に接続していきます．このとき，すべてを最大連結成分に接続するのが最適であることが証明できます．（その他成分が 2 個あるときにまとめた方が良いことを示せば，その他成分が 1 個のときに帰着できます）．
B. Hongcow’s Game
$k=0,1,\ldots,9$ の順に，
- $2^k$ の位が $0$ であるような $i$ 全体
- $2^k$ の位が $1$ であるような $i$ 全体
を質問します．ここから各 $i$ について，$i$ が該当しない質問全体の min をとると答になります．なぜならば $j\neq i$ ならば，$j$ を含み $i$ を含まない質問が存在するからです．
C. Hongcow Buys a Deck of Cards
bit dp を考えます．例えば「これまで獲得したカードの集合」「これまでのターン 1 の回数」という量だけだと，現時点で残っている token の量が読み取れなくなります．
「これまで獲得したカードの集合」「これまでのターン 1 の回数」「これまでのカード獲得時の red の割引量」「これまでのカード獲得時の blue の割引量」などを考えます．割引料というのは $r_i$ とのコストの差分です．割引量が分かるとターン 1 の最小回数も分かるので，これは考えなくてよいです．よって $3$ つの量「これまで獲得したカードの集合」「これまでのカード獲得時の red の割引量」「これまでのカード獲得時の blue の割引量」に対して boolean を定める dp ができます．これは「これまで獲得したカードの集合」「これまでのカード獲得時の red の割引量」に対して「これまでのカード獲得時の blue の割引量」の max を持つ dp にして高速化できます．最大で $2^16\times(1+2+\cdots+16)$ 程度の状態数．
D. Hongcow Draws a Circle
赤点が青点の凸包の境界または外側にあるときはいくらでも大きくできます．
内部のときはいくらでも大きくはできません．極大な状態では $2$ 個以上の青点を通っています．
これら $2$ 個の青点を固定して考えます．
このような $2$ 点は円の中心から見ると，青点の中で最寄りの $2$ 個です．（適当なタイブレイクのもとで）このような組の候補はボロノイ領域が隣り合う $O(M)$ 組に限定できます．
この $2$ 点組を固定した上で $O(N+M)$ 時間で解きます．固定した $2$ 点を通る円を考える上で，残りの点は適当なソート順を定めることができます（円周角の定理から）．特に赤点についても青点についても，$2$ 点を結ぶ線分に最も「近い」（円周角が $180$ 度に近い）$2$ 点を定めることができて，それら定数個の点について適当な判定を行えばよいです．
$O((N+M)\log(N+M))$ 時間などでも解けるのではないかと思いますが…．
E. Hongcow Masters the Cyclic Shift
尺取りをすることにして，$O(n)$ 回の判定問題が解ければよいです．
good というのは，$w_i = L+R$ と空でない文字列に分解したときに，$R$ からスタートして「$X$ の要素の追加」「$X$ の要素であるような prefix の削除」を繰り返して $L$ を作れないということです．
状態は常に $X$ の要素の prefix です．これらを頂点として有向グラフを作り，サイクルがあったらアウト，という判定をします．
