yukicoder contest 371 (Asakatsu Presents)

　Dまで四完。

コンテストへのリンク

No.2157 崖

　自力ACだけど時間がかかった。

　普通に考えると三乗のDPになるけれど、それをどうやって高速化するか、という問題。

　まず、各D[i]をソートしておき、

・DP[i][j]=D[i][j]を使うときの、最小のfの値

　としたとき、

・DP[i][j]のままいけるのは、D[i+1]の値が、D[i][j]以上D[i][j]+DP[i][j]以下のとき

・それ以降は、D[i]の差に従って増えていく

　なので、前者を（双対）セグ木を使って更新。後者は別の配列を用意して求めた。

　実装大変だった割にたくさん解かれているなぁ、と思ったら、答えで二分探索すれば実装が楽だった模様。答えで二分探索は最初考えたけれど、なぜかできない気がしてやめてしまった。