きろく

特筆すべき記録のまとめ

AtCoder Beginner Contest 117:C - Streamline

問題

atcoder.jp

解法

まず,駒を +1 の方向に動かした後に -1 の方向に動かすのは自明に意味がない.なので,駒を +1 の方向にだけ動かすことを考える.駒が通る距離を最小化したいので,駒が通らない距離を最大化すればよい.一番左・右の地点より外側のところに駒を置くのは自明に意味がないので,駒が通る最大の距離は一番左・右の地点の間の距離となる.ここで,隣り合う地点間の距離をすべて求める.すると,これらの距離のうち大きいもの (N - 1) 個を駒が通らないようにすれば題意を満たせる.駒が地点の数以上にある時に注意.O(MlogM).

解答

atcoder.jp

f:id:babcs2035:20190211221650p:plain