Kotlin Heroes: Episode 2

Kotlin Heroes はコンテストには参加せず，C++ や Python で書いたコードを chatgpt に変換してもらうことで AC しています．コンテスト中にこれをやるのはルール違反です．

A. Three Problems

$3$ 回ループして，前回より大きい中で最も小さいものをとっていきます．

最大値のうち最も列の後ろにあるところ．

全部 $a_i$ ずつとったあと，コストの低いものから順に貪欲にとっていきます．

$k$ の倍数の等比数列のところだけ抜き出すと，列があって隣接 $2$ 項から $(a,b)$ を引く（負になってはダメ）という問題になります．$a\geq b$ のとき左端，$a\leq b$ のとき右端から貪欲にとってよいことが証明できます．

答の二分探索で，判定問題を解きます．1, 2, …, n はちょうど $2$ 回でなくてはいけないし，左側・右側の出現だけとっていったときに同じ列が $2$ 個できないといけないというのが条件になります．

各文字列は kotlin の何文字目から何文字目まで進むというようにして，$6$ 頂点のグラフにおける有向辺と見なせます．eulerian walk を作れということになります．使う辺を試すたびに連結性を確認して作りました．

simple path と限らないと書いてありますが，結局 simple path としてよいです．両端は初期色と違う点だとしてよいです．よって，初期色と違う点を集めた点集合の直径をどっちか方向に進むという $2$ 通りが解の候補になります．

二分探索します．判定問題を木DPで解きます．

各 subtree に対して，木 dp の返り値は，valid な塗り方に対して親辺と同じ成分の辺の個数としてありうる最小値とします．木 dp の中で，「dp[a] := 色 1 の個数が a のときの色 2 の個数の最小値」という感じの dp をします．復元があるのが大変でした．

近傍の頂点集合が同じ頂点は，同じ値が割り当てられているとしてよいです．そうでなかったらまとめられるため．なので，結局入力のグラフは $16$ 頂点以下だとしてよくなります．

あとは，1 頂点ずつ決めていきながら適宜自明な枝狩りするという再帰関数を書いたら AC になりました．

ちゃんとは見積もっていないのですが…．

どんなに大きくても $15!$ （最初の頂点は $0$ としてよい）ですし，$15!$ もかかりそうな状況では辺が密なので少し探索するたびにどんどん枝狩りされていきそうだというのが直感です．

二部グラフを使った何かも考えようとしましたが，連結性が保証されないのでやりにくいのと，そういう類の制約は普通に再帰するだけでも勝手に考慮されるはずなので不採用．