- https://codeforces.com/contest/1413
- https://codeforces.com/contest/1434 (div1)
- https://codeforces.com/contest/1435 (div2)
A. Perform Easily
使う値の最大値を増やしながら，最大コストになっているものの割り当てを変えていきます．
B. Shurikens
最も安いものは，それが出ていく直前の挿入で入ったとしてよいです．安いものから順に決めていき，最後に妥当性を確認します．
C. Solo mid Oracle
$a>bc$ ならばいくらでも可能です．そうでないとき $c$ 秒より手前だけ考えればよく，すると $x$ 回目のスキル発動時点での与ダメージが $x$ の多項式関数になります．これの最大値を求めればよいです．
D. Roads and Ramen
根から各点までの石の個数によって，頂点を $2$ 色に塗り分けたとします．同色の点の直径を求めよということになります．
点集合の直径はセグメント木で扱えるので，色 $0$，色 $1$ の直径をセグメント木で管理します．辺の反転が来ますが，これは部分木内の頂点の色の反転に対応するので，遅延セグメント木を使えば ok です．
E. A Convex Game
各列に対する grundy 数を求めればよいです．
列を固定すると，$2$ 手目以降の状態は最後の $2$ 回に選んだ要素としてよいです．そこで $\dp[i][j]$ を最後の $2$ 手が $(A[i],A[j])$ であるときの grundy 数として多項式時間では解けます．
このゲームは高々 $O(\sqrt{A})$ 時間で終了するため，grundy 数も $O(\sqrt{A})$ です．
そして，上の dp テーブルには列ごとに単調性があります（$\dp[i][j]\leq \dp[i+1][j]$）．これはオプションの集合に包含があるからです（なお行方向には単調性はありません）．
したがって，$DP[j][k]$ を，$dp[i][j]\geq k$ となる最小の $i$ などとして，状態数 $O(N\sqrt{A})$ の DP ができます．これを高速化します．
$\dp[-][j]$ を決めるには，各 $k$ に対して，$\mathrm{mex}(\dp[j][x],\ldots,\dp[j][N-1])\geq k$ を満たす最小の $x$ があればよいです．そのためには，$\dp[j][x]=k$ となる $x$ のうち最大のものだけを保持しておけばよいです．
したがって，$\dp[-][j]$ 部分を決めたら，各 $(i,k)$ に対して $\dp[i][j]=k$ となる $j$ が初出であるか否かを調べて，初出の部分があればそこを記録しておくということをします．これを64分木で行えば，全体で $O(N\sqrt{A}\log N)$ 時間で解けます（$\log N$ は64分木由来なので定数倍は小さい）．
