A. A Twisty Movement
$O(N)$ 時間.結局列を 0, 1, 2, 3 の 4 部分に分けて(空でもよい),0, 2 番目にある「1」と 1, 3 番目にある「2」の個数の合計を最大化すればよい.最後の要素がどの部位かをもって dp.
B. A Determined Cleanup
$f(-k)=p$ という条件です.定数項から順に決めていけます.
C. A Colourful Prospect
euler の公式により領域の個数を求めます.基本的には連結成分と交点の個数を数えるだけですが,3 点が交わるか否かの判定も必要になります.
D. A Creative Cutout
$x$ を固定するごとに,$y$ について適当な範囲で適当な多項式の和を求めることになります.和の明示的な公式を求めてもよいですし,多項式補間などを利用してもよいです.
E. A Preponderant Reunion
似ている:https://atcoder.jp/contests/jsc2023-final/tasks/jsc2023_final_e
まず次のように一般化した問題を考えます.
- 隣接する 2 項に対して好きな $x\geq 0$ をえらび $x$ ずつ引く操作を許す.$A_i$ が負になることも許す.
- 目標はどの隣接する 2 項にも $0$ 以下の要素が存在するようにすること.
後者の条件は言い換えると次のようになります:「いくつかの項は無視できる.ただし無視する項が隣接してはいけない.無視していないものは $0$ 以下にする必要がある.」
無視していないものが $3$ つ並ぶような方法は,その真ん中を無視してもよいので,無視していない項は $2$ つ以下しか並ばないとしてよいです.すると,無視しない項を間に 1, 2 個はさんで無視する項を並べる形になるため,これは dp で簡単に最適化可能です.間に無視していない項 $x$ があるならコスト $x$.間に無視していない項 $x,y$ があるならコスト $\max(x,y)$ といった形になります.
この新問題の最適コストをもとの問題設定でも実現可能であることが分かります.まず,新問題の最適解であって,すべての要素が負にならないものが存在します.はじめて負の要素を作る操作は無駄であるか引く場所をずらすことで負の要素を作らないようにできるからです.さらに,引く値は常に $x=\min(A_i,A_{i+1})$ であるようにもできます.これは長さ 1, 2 の部分を 0 にするだけなので少し場合分けすれば分かります.よって新問題の最適コストをもとの問題でも実現可能であることが分かりました.