読者です 読者をやめる 読者になる 読者になる

競技プログラミングをするんだよ

ICPC国内予選突破を目標に一日一問題以上解いていきます。

yukicoder 「No409 ダイエット」

yukicoder

作問しました.

解説を書きます.
実はなんですけど4/9が誕生日なので問題番号が409でちょっと嬉しかったです.

解説

動的計画法をします.

TLE解法その1(ストレス値をパラメータに組み込む)

愚直にO(N^2)のDPをしようとすると以下のような漸化式になると思います.

F_{k,s}:= k日目でストレス値がsのときの体重の最小値

すると,状態遷移は以下のようになります

初期状態:F_{0,0}=W , F_{0,1}=,,,=F_{0,N}=\infty
状態遷移:
F_{k,0}=min_{0 \le i \le N} ( F_{k-1,i}+ D_k)
F_{k,i > 0 }=F_{k-1,i-1}-A+iB

最終的に,min_{0 \le i \le N} ( DP_{N,i})が答えになりますね.

しかし,この解法では計算量がO(N^2)になってしまいます.

先ほどの漸化式をよく見ると,DAGとしてみたとき状態遷移の辺がかなり少ないことが分かります.
このままでは無理なので別の漸化式を考えてみましょう.

TLE解法その2 (ドーナツを食べた日だけを求めるDP)(より想定解法に近い形)

F_{k}:= k日目でドーナツを食べたときの最小値

t日間ドーナツを食べなかった時の体重の変化量は
-t*A +\frac{t(t+1)}{2}*B と表せるので,

F_0 = W
F_{k}=min_{0 \le i \le k-1}(D_k + F_i -(k-i-1)A +\frac{(k-i+1)(k-i)}{2}B)

答えはmin_{0 \le i \le N}(F_i -(k-i-1)A + \frac{(N-i+1)(N-i)}{2})になります.

convex hull trick解(想定解法)

上記の解法でも,まだO(N^2)です.
しかし,漸化式の中でiに依存しない項が現れると思います.
上の漸化式を変形すると

F_{k}=D_k-(k-1)A+\frac{k^2-k}{2}B+min_{0 \le i \le k-1}(-iBk+F_i +iA +\frac{i^2+i}{2}B)

iを定数とすると,以下のa_i,b_iも定数となります
a_i=iB
b_i=F_i +iA +\frac{i^2+i}{2}B

すると
F_{k}=D_k-(k-1)A+\frac{k^2-k}{2}B+min_{0 \le i \le k-1}(-a_ik +b_i)

となるので,y=-ax+bの形をしたk-1本の直線のうちx=kの時yが最小となるものを選べばよいことになります.
選んだ最小値のものから,F_kが求められ,a_k,b_kも求められるので,新たにy=-a_kx+b_kという直線を直線群の中に追加します.

a_iの値が徐々に大きくなるので,"convex hull trick"というテクが使えます.
蟻本のdequeの紹介のページに載っているアルゴリズムで,これを用いるとO(N)で解くことができます.