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
関連：https://yukicoder.me/problems/no/1770
$M$ が偶数のときは簡単です．$M+1$ を法として，$(x,M+1-x)$ ととるタイプの戦略を考えればよいです．$M$ は奇数だとします．
$dp[n]$ を，$n$ からゲームを始めたときの勝ち状態とします．禁じ手はひとつ以下なので，各 $n$ について勝利方法を高々 $2$ 個保持していれば十分です．これを適切に実装すれば $O(N+M)$ 時間程度で解けるというのが上の yukicoder の問題です．
勝利方法の個数に注目します．「$0$ 個」「$1$ 個」「$2$ 個以上」の $3$ 通りがあります．勝利方法が $0$ 個であるような $n$ 全体の集合 $S$ を求めていきます．$S={\ldots,-2,-1,0}$ からスタートして，非負の部分 $a_0,a_1,a_2,\ldots$ を求めていきます．
重要な性質として $a_{i+1}\in \lbrace a_i+M+1,a_i+M+2\rbrace$ が成り立ちます．次の議論から分かります．
– $a_i+1\leq n\leq a_i+M$ に対して勝利方法は $1$ 個以上ある．$a_i$ に行くようにすればよい．
– $n=a_i+M+1$ に対して勝利方法は $1$ 個以下である．$(M+1)/2$ 以外の選択だと $a_i$ に持っていかれてしまうため．
– $n=a_i+M+1$ の勝利方法が $1$ 個であるとする（つまり $(M+1)/2$ だけ）．このとき，$n=a_i+M+2$ での勝利方法は $0$ 個である．まず，$2$ 以上だと $a_i$ に持っていかれてしまう．$1$ だと仮定から $(M+1)/2$ をとられて負け．
したがって，このような値は $N$ 以下に $O(N/M)$ 個しかなくて，これをすべての $M$ について前計算しておけば解けるだろうという方針になります．
$a_{i+1}$ を求めるには，$a_i+M+1$ に勝利方法があるか否かをチェックすればよいということになります．一般に $n\leq a_i+M+1$ に対して勝利方法をすべて求めるという問題を考えます．
上では勝利方法は $0$ 個，$1$ 個，$2$ 個以上のどれかということを書きましたが，実際にはその候補は $O(1)$ 個しかありません．たいていの選択肢は $a_i$ または $a_{i+1}$ に持っていかれて失敗だからです．
よって計算量を無視すればメモ化再帰で解けます．実際に試すとこれで十分高速です．$O(1)$ 個の選択肢といっても，ある選択肢は $a_i$ までの距離が偶数であるとき限定の選択肢などになっていて結果的に探索量は少ないようです．公式解説でも何かの偶奇が $1/2$ ずつだろうという仮説のもと見積もっていて，あとは実際に実行してみれば確かに高速という議論だと思います．
