Kotlin Heroes はコンテストには参加せず，他の言語で書いたコードを chatgpt に変換してもらうことで AC しています．コンテスト中にこれをやるのはルール違反です．
A. Furniture Store
手前の min 以上のものを出力します．
B. Games
共通でない要素があればそれを出す，を反復します．
C. Minimum on Subarrays
$L\leq R$ となる格子点 $(L,R)$ を走査すると思います．
$L$ が偶数のときは $R$ を昇順，$L$ が奇数のときは $R$ を降順に処理すればよいです．
D. Avoid Minimums
目標となる定数は，$K$ 回で到達可能なもののうち最大のものとしてよいです．
各 $x$ について $x\to x+1$ という加算でコストが発生する回数を考えます．
これは $\min(a)$ から目標値までの間で $1$ 回ずつあって，$x=\min(a)$ のときには複数回必要です．
ここからスコアの上限が出てきますが，大きいもの優先で操作すればそれが達成可能です．
E. Perfect Cut
実験を書くと，0111111111 のようなもの以外であれば条件を満たすことが分かります．
証明を考えると，
- 1****** なら prefix を長さ $1$ にすればよい．
- 00***** なら prefix を長さ $1$ にすればよい．
- 010**** なら prefix を長さ $2$ にすればよい．
- 0110*** なら prefix を長さ $3$ にすればよい．
などとして証明できます．
F. Array Reduction
$\mathrm{ANS}[i]\geq \mathrm{ANS}[i+1]$ はすぐに分かるので，なるべく要素数を減らす操作だけが問題です．頻度列を並べてヤング図形を考えると，先頭行や先頭列を削除すると考えます．
ヤング図形のマスの個数に比例する計算量をかけても $O(N)$ 時間であることに注意して，最も左上に残るマスごとに回数や残る個数を計算します．
G. Good Robot Paths
最大長方形のアレ．長方形を数えますが，長さ $1$ の辺があるか否かで $1$ 倍や $2$ 倍で答に足します．
横に連続するマスをとって，そこが底辺となる場合を計算します．
だいたい次のような問題になります：
列 $(a_1,\ldots,a_n)$ がある．$\sum_{i<j}\min(a_i,\ldots,a_j)$ を求めよ．
$j$ をインクリメントしながら $\mathrm{ans}[i]=\min(a_i,\ldots,a_j)$ という列 ans を管理することを考えると，$O(n)$ 回の区間変更になって，総和も差分更新できます．
H. Merging Vertices in a Graph
操作回数最大化の方が簡単です．操作を $1$ 回以上行えるならば $N-1$ 回行えます．
辺がない $2$ 頂点 $a,b$ をとって，$v\neq a,b$ を $a$ にマージしていけばよいです．
操作最小化について考えます．
$S=\{v_1,v_2,\ldots,v_k\}$ をマージしてできた頂点が条件を満たすとします．他の頂点のマージの有無は条件達成に無関係なので，$S$ を $1$ 点にまとめる操作だけが行われるとしてよいです．このとき，補グラフにおいて $v_i$ と隣接している点はすべて $S$ に含める必要があります．
結局，$S$ は補グラフにおける $1$ つ以上の連結成分の和集合です．補グラフを連結成分分解して，最小の大きさの連結成分 $1$ 個を $S$ とするのが最適です．
I. Color the Tree
多項式時間で解くことは可能ですが，実装が大変そうなので，もうちょっと単純な探索にしてさぼりました．
操作を逆順に考え，操作は上書き不可能な着色だと思います．
葉が偶数個の場合には，葉の $2$ 個組をとっていきます．葉が奇数個のときは，「葉をひとつ，未着色の頂点をひとつ選ぶ（一致してもよい）」という操作が $1$ 回まで許可されることになります．
葉を $n$ 個だとすると，下手にやっても $2^n\cdot \mathrm{polynomial}(n)$ みたいな計算量になりそうです．
やばいのは葉がたくさんあるときです．そこで，次のようにしました：
ある $v$ の近傍に葉が $c_1,c_2,c_3,…$ とあるとする．このとき，$c_i$ が未着色のときに $c_{i+1}$ を選ぶことはできない（代わりに数え上げのときに，相応の係数をかけて数える）．
計算量見積もりですが，例えば葉の状態数を考えると，次のような見積もりになります：$a_1+a_2+\cdots+a_k+k\leq 32$ であるような組について，$\prod(a_i+1)$ 通り．これは $118098$ が最大のようで，パスに葉を $2,2,2,2,2,2,2,2,2,2,1$ 個ずつつけた caterpiller の場合です．この場合は，探索中に現れる状態は $799689$ 通り程度あるようで，私の C++ プログラムでは手元 1 秒弱，AtCoder コードテスト環境での Kotlin では 3200ms 程度．これが最悪ケースかはわからないですが，あまり安易には Hack できない程度の解法にはなっているということでいいのかなと思いました．
