問題 D - Equal Cut 長さ N の整数列 A を４つの連続する部分列に分けたとき、４つの数列のそれぞれの和の最大値と最小値の差を最小化すると差はどうなるか、という問題。 解法 ４つに分けるので半分の半分だと考える。最初に半分に切るところは全通り試すと…

問題 E - Range Minimum Queries 長さ N の数列 A から「長さ K の連続する部分列を１つ選び、その中の最小値を数列から取り除く」動作を Q 回行う。Q 回で取り除いた Q 個の数値の最大値と最小値の差の最小値を求める問題。 解法 最小値を固定させると、ま…

問題 E - すぬけ君の地下鉄旅行 / Snuke's Subway Trip N 個の駅と M 個の路線があり、各路線には運営会社が決められている。同じ運営会社で連結の路線はどれだけ乗ってもコストはかからないが、運営会社をまたいで載る場合はコストがそれごとに１かかる。こ…