A. Game of Life
1 はずっと 1 なので,1 ではさまれた区間ごとに考えて解けます.1 が増加する回数は N 回以下なので,min(N,M) ステップ分シミュレーションしてもよいです.
B. Lord of the Values
偶数制約に注意.$n=2$ を $6$ 回で解けます.
C. Compression and Expansion
$x$ を足せるようななるべく長い prefix を残して $x$ を追加する貪欲.
D. Love-Hate
$n/2$ 人以上に該当する人をひとり固定すると,候補となる通貨の種類が $15$ 以下になるのでやりたい放題です.このひとりを乱択して解くことを繰り返します.
E. Crypto Lights
各 $n$ に対して,$n$ 手以上かかる確率を求めて,足せばよいです.
F. Favorite Game
状態として次を考えます.
- activate されている集合が $s$ で,タスク $i$ を完了した.このときのタスクの個数の最大値は?
- $k$ 個のタスクが完了している状態で activate されている集合がちょうど $s$ になった.このときの時刻の最小値は?
後者について,activate 集合が増えたタイミングで現在地はすべて同一視されるので,現在地は持たなくてよいです.あとは次に activate set または完了したタスクが増えるという遷移をすべて実装すればよいです.
G. Try Booking
次のようなシミュレーションを考えます:$[L,R)$ 内で条件を満たす最小インデックスの区間 $[l,r)$ を見つける.そのあと $[L,l)$ および $[r,R)$ に対する同様のシミュレーションを再帰的に行う.
これで,$O(|ans|)$ 回の「見つける」によって答が求められます.$x=1,2,\ldots,N$ に対する答の総和は調和級数 $O(N\log N)$ であることから,$O(N\log N)$ 回の「見つける」ですべての答えを計算できます.
見つける部分は矩形クエリで $O(\log^2 N)$ 時間かけると計算量 $O(N\log^3N)$ 時間でこれで AC しました(想定解と同じ計算量でした).答の総和が $N\log N$ 近くなる最悪ケースを作るのは非常に難しそうなので最悪見積もりは速くなりやすいと思います.
H. Hopping Around the Array
比較的普通の binary lifting テクニックです.
ある移動においてスキップ回数も固定したとき,「貪欲な進み方」があります.最後の一歩は例外で,それ以外は次の次に行ける場所が最も遠い場所を次の場所とします.そこで,
- dp[i][j][k]: $2^i$ ステップ貪欲に進む,$j$ 回までスキップしてよい,マス $k$ から進んだとき
が前計算できます.よく知られた手法にスキップ回数の二重ループを加えるだけです.
答を求める二分探索も,ステップ数を二分探索しながら,スキップ回数ごとの行き先を保持するようにして行えます.