AtCoder Regular Contest 105 C - Camels and Bridge

問題リンク
atcoder.jp

問題概要
頭のラクダがおり, それぞれ重さが決まっている
いま任意の順番にラクダを並べて, 個の橋を渡ろうとしている. 橋には長さと耐久値が決まっており, その橋に乗っているラクダの総体重が耐久値を超えた場合, 崩れてしまう. そのためラクダ間の間隔を十分にとる必要がある.

橋を渡り切れる場合の先頭のラクダと末尾のラクダの距離の最小値を求める.

考えたこと
橋の順番は関係ないため, 橋の耐久値ごとに長さをまとめておく.
あるラクダの集合を考えて, その重さの総和をもとに橋を渡り切れるか考えると, 耐久地が[0 ~ 重さの総和-1]のうちで最も長いもの以上の距離をとれば渡り切れることがわかる. 最大値を求めるのは耐久値を座圧してSegment Treeを使うことででできる.
ラクダの集合同士の距離の更新は区間dpのようにすればよく, いま閉区間[i, j]を見ているとすると, 先ほどの最大値及びdp[i][k]+dp[k][j]を見ていけばよい.

順列を全て試すので, 全体の計算量はになる

提出コード
atcoder.jp