A. Dungeon Equilibrium
$x$ の個数を数えて，$x$ 個以上だったら $x$ 個残す．そうでなければ全削除．
B. Expansion Plan 2
$8$ 方向移動が $a$ 回以下と $4$ 方向移動が $b$ 回以下で $(0,0)$ から $(x,y)$ まで到達できますか？と言い換えられます．
$8$ 方向移動で各座標を貪欲に $0$ に近づけたあと，マンハッタン距離が $a$ 以下になれば成功です．
C. Meximum Array 2
- ある min 区間に含まれ，ある mex 区間に含まれる：$k+1$ 以上の数しか書けない．何を書いても関係ないので $k+1$ を書く．
- どの min 区間に含まれず，どの mex 区間に含まれない：何を書いても関係ないので自由に埋める．
- ある min 区間に含まれ，どの mex 区間にも含まれない：$k$ を書く．（条件を満たす書き込み方があったとして，$k$ でなかった場合に $k$ に取り換えても条件を満たす）．
一番難しいのは，「どの min 区間に含まれず，ある mex 区間にも含まれる」ような部分への対応です．これが一番難しいですが，そのようなマスのうち連続 $k$ 個で $0, 1, \ldots, k-1$ がコンプリートできるように出来ると嬉しいです．これは実際可能で，そのようなマスのうち $i$ 番目に $i\bmod k$ を書くようにすればよいです．
D. Billion Players Game
絶対値がついていますが，かなり見掛け倒しです．「何もしない」「$x-a_i$ を獲得」「$a_i-x$ を獲得」が選べます．
「何もしない」は $2$ 種両方を選ぶことと等価です．よって
- 各 $i$ について，$x-a_i$ を獲得するか選ぶ．
- 各 $i$ について，$a_i-x$ を獲得するか選ぶ．
を独立にやってよいです（ある $i$ について両方選ぶ場合を含めても解が変わらない）．
前者を $p$ 個，後者を $q$ 個選ぶとします．ワーストケースの $x$ は，$p,q$ の大小関係に応じて $x=l,r$ のどちらかです．
$p\leq q$, $q\leq p$ それぞれで解きます．選ぶ $a_i$ は昇順や降順で $p$ 個や $q$ 個であり，スコアは $f(p)+g(q)$ の形で書けるのであとは簡単な計算です．
E. Adjusting Drones
難しかった．
【気づきその 1】シミュレーションは頻度列だけでできます．（各 $x$ の登場回数が分かっていれば，次ターンの各 $x$ の登場回数も決まる．）
頻度列のヒストグラムを考えると，高さ $2$ 以上の部分が右にスライドするという雰囲気の操作になります．
【気づきその 2】（全部 $K$ 個以下になっても操作をやめないことにして）「最大頻度」は単調減少する．
これは上のシミュレーション方法を考えると分かります．時刻について二分探索可能になりました．あとは「$t$ ステップまとめてシミュレーション」ということが出来ればよいです．これは，右側から順に見ていけばよいです．右側から順に余剰分を見て，$t$ 個以下進んだところに高さ $0$ のところがあればそこに移動．そうでなければ右に $t$ 個進むということになります．
F. Git Gud
はじめに考えたのは次の解法でした．
- (15,1),(13,1),(11,1),…,(1,1)：全部偶数に変化
- (14,2),(10,2),(6,2),(2,2)：全部 $4$ の倍数に変化
- $\vdots$
コストは（確か） $220$ 万程度になって足りていません．
$2$ 進法を $3$ 進法に変えるなどの一般化を考えます．
- (14,1),(13,2),(11,1),(10,2),…：全部 $3$ の倍数に変化
- (15,3),(12,6),(6,3),(3,6)：全部 $9$ の倍数に変化
これが（$k$ 進法にしても）全然ダメで困ります．
コスト目標値を考えると，$1$ マスに書く $l$ は平均で $4$ 以下におさめなければならないです．またペナルティ $1000$ の方がいまはかなり少ししか使っていません．このバランスを是正することを考えて冷静になると，次のようにすればよかったです．
- (13,1),(10,1),(7,1),(4,1),(1,1)
- (14,1),(11,1),(8,1),(5,1),(2,1)：ここまでで全部 $3$ の倍数に変化．
- (12,3),(3,3)
- (15,3),(6,3)：ここまでで全部 $9$ の倍数に変化．
単調性のペナルティが増えて，$l$ は平均的に小さくなって，全体としては改善です．
これを $3$ 進法から $k$ 進法に変えて，$k$ を探索していくと，例えば $63\leq k\leq 120$ 程度にすれば成功するようです．
G. Isaac’s Queries
まず，ランダム生成だと半分くらいは $29$，$1/4$ くらいは $28$，等の答えだと想定できます．
まず，$29$ である場所を低コストで決めたいです．クエリごとに，$2^{29}$ の位が等しいか否かが分かるので，potentialized unionfind によって，連結になるようにクエリすればできることが分かります．左右両端を聞いたあと，他のものを遠い側の端とクエリするようにします．
$2^{29}$ の位が等しいグループに分割したら，各グループ内で，$2^{28}$ の位がどうなっているかを同じように調べていきます．
コスト $10$ に収まるかは全然見積もれませんでしたが，実装してみると十分足りていました．
H. Keygen 3
実験 → 未証明 AC．
とりあえず bitonic な列は $2^{n-1}$ 個しかないので，実験が $n=25$ 程度までは十分回ります．
$K=N-M$ とするとき，$K$ を固定すると列の個数が，収束していそうな感じがします．
（十分大きな $N$ で “1 2 4 10 22 48 106 230 494 1060 2260 …”）
実装したもの：$(N,M)$ の解について
- $N$ が小さいなら愚直
- $M\geq 2$ なら $(N-1,M-1)$ として生成して先頭に最小値を追加する．
- $M=1$ ならランダム bitonic permutation で当たり待ち（確率 $1/N$ 程度で引けると信じると $2000$ 個くらいは作れる）
解が $2000$ 個未満のところで，$N$ が大きくて $(N-1,M-1)$ からは作れないという解があると WA になるので，この難易度ならそういう例外と戦う必要があるかと思ったのですが，提出してみたらこれで AC でした．
I. Hyper Smawk Bros
まだ．（この問題 を調べにいったのですが）
