KUPC2019

ちょっと気になった問題取り上げます。

https://atcoder.jp/contests/kupc2019/tasks/kupc2019_e

木ごとにgrundyするのかなと思ったんですが、ゲームが分割されているわけではないので今回では
あんまり役に立たないです。木ごとに単なる勝ち負けを求めても、最適moveではわざと負けるみたいな
ことをする可能性もあります。なので、(i)「手番が必ず変わらない」(ii)「手番が必ず変わる」(iii)「手番が変わるかを先手が選べる」
(iv)「手番が変わるか後手が選べる」の4パターンに分類すると良いです。
すると複数の木を見て回った後の勝敗も上の4パターンに分類できます。しかし(i)は無視できるので実質3パターンです。
(iii)が一つでもあるなら、残りのN-1の勝敗パターンを見てから先手が決められるので先手の勝利です。
(iii)がないなら、(iv)を先に選んでしまうと後手が残りの木の勝敗を見て勝利するように行動できるので負けです。
よって(ii)を順番に選んでいくゲームになり、(ii)が偶数個なら後手勝ち、奇数個なら先手勝ちとなります。

https://atcoder.jp/contests/kupc2019/tasks/kupc2019_f

まず区間ではモンスターを一点集中させるのが良いことを証明できます。これは簡単で、
区間でb_l,...,b_rとモンスターを配置したなら、argmin(A_i-b_i)に集中させても解は小さくなりません。
事前にどの地点にモンスターを配置するか決めてしまえば、解は(区間のうち配置地点を含むものの和)-(配置地点の勇者の数)
となります。ここで
dp(i):=0~i地点まで見てi地点にはモンスターを配置すると決めた時のコストの最大値とすれば、
dp(i)からdp(j)への遷移は(始点が(i,j]でjを含むような区間の和)-A_jとなり、これはjで平面走査すればO(NlogN)で行えます。
全てのiについて見ていっても合計でO(N^2logN)です。

https://atcoder.jp/contests/kupc2019/tasks/kupc2019_g

abca
bcab
cabc
abca

これが思いつけるかが全てです。あとは端を延長することによって達成できます。