脳log[20211115]

2021年11月15日 (月) [AtCoder] 精進。PAST202107-H「折れ線グラフ」。配置的に茶～緑 diff だと思うんだけど初見では解けていなかった>20210721p01.08。特徴的な制約を見れば３乗の DP の臭いがプンプンするが、当時はそれも見えなかった。「Ruby によるすべての提出」。AC は２つ。工夫なしの４重ループ(N 個の点、残りの Y 座標、直前の Y 座標、今回の Y 座標)は通らないはず。目指すグラフの形はゆっくり平均値(のちょっと上？)まで上昇してゆっくりゼロまで下降する折れ線なので、そのあたりを織り込んで端折れる遷移がある。……というか、自然な延長として DP の必要すらないと思うんだけど、どうなんでしょうね。Math.sqrt(a*a+1)+Math.sqrt(b*b+1) と 1+Math.sqrt((a+b)*(a+b)+1) の大小関係は。何をどういう a と b に分割するのが最適かはやっぱり DP をせんとわからんのかな。■いろいろと半分にして答えが出るかと思ったけどなかなかうまくいかない。