A. Data Recovery
min より小さいものや max より大きいものがあると矛盾です.min, max はなければ追加する必要があります.あとはたとえば min をたくさん追加すれば個数が合わせられます.
B. Spyke Chatting
各 chat ごとのメッセージ数を集計しておき,そこから答を求めます.
C. Jeopardy!
選ぶ問題順をスワップする議論で最適解の構造を考えると,regular question を最初に全部とってしまい,その後 auction question を降順に使えばよいと分かります.
D. 2048
一度列の状況が $\ldots, a, b, \ldots$ かつ $a<b$ となったら,この $a$ から左は二度と変化することはないので,ゲームから除外して考えればよいです.
このように除外しておくと,列の状態は常に単調減少列で,値の総和と一意に対応します.状態が $0, 2, 4, \ldots, 2048$ のどれかとして表せて,あとは dp で答えが求まります.
E. Maze 2D
変更クエリがない場合,左から順に $2$ 状態の dp で解けます.これは,min-plus semiring 上の $2\times 2$ 行列の総積という形で答が求まることを意味します.これをセグメント木で持てばよいです.
