summerFestivalContest Treasure Hunt
問題ページ
Hamako Online Judge
罠
n回加算すべき崖と崖の間の道を一回分しか加算していなかった。
学び
3分探索の分割でx1=x0+(x3-x0)/3, x2=x0+(x3-x0)*2/3と書いていたがx1=(x3+2*x0)/3, x2=(2*x3+x0)/3で書ける。
解法
橋がある座標をそれぞれx_1, x_2とする。n人の子供の総移動距離をf(x_1, x_2)とすると、この2変数関数の最小化を行う問題に帰着できる。x_1を定数cに固定して考えると、f(c, x_2)は凸関数である距離の総和なので同様に凸関数である。したがって、f(c, x_2)は3分探索で求めることができる。x_1について3分探索を行いその3分探索の中でさらに3分探索を行う。
