JOI 水ようかん (Mizuyokan)

問題

D - 水ようかん (Mizuyokan)

解説

まず、最小値と最大値の候補はN²個ずつである。

(1) そこで、N⁴通りについて、それぞれ実際に切り分けられるかの判定の方法を考える。
dp[i] := [0,i]を条件を満たすように切り分けられるか(bool)
[0,i]について、0<=j<=i-1を満たすjをとって、区間を[0,j],[j+1,i]に分けて考える。dp[j]=trueのとき、
最小値<=L_(j+1) + ... L_i<=最大値
を満たすならばdp[i]=true。よって判定には全体でO(N²)。全体でO(N⁶)かかる。

(2) 真偽値をとるDPには無駄が多い(蟻本より)。最小値を固定すると、知りたい情報は「条件を満たすように切ったときの最大値の最小値」。ここまでくれば先ほどと同じようなことをすればO(N²)でそれぞれの候補について計算ができる。全体でO(N⁴)。

感想

これ本当に難易度7か？？？とても教育的な気がする。分かると楽しい。