babcs2035 https://blog.hatena.ne.jp/babcs2035/ きろく https://babcs2035.hateblo.jp/ 競技プログラミング AtCoder 300 点問題 問題 解法 解答 問題 atcoder.jp 解法 まず，駒を +1 の方向に動かした後に -1 の方向に動かすのは自明に意味がない．なので，駒を +1 の方向にだけ動かすことを考える．駒が通る距離を最小化したいので，駒が通らない距離を最大化すればよい．一番左・右の地点より外側のところに駒を置くのは自明に意味がないので，駒が通る最大の距離は一番左・右の地点の間の距離となる．ここで，隣り合う地点間の距離をすべて求める．すると，これらの距離のうち大きいもの (N - 1) 個を駒が通らないようにすれば題意を満たせる．駒が地点の数以上にある時に注意．O(MlogM)． 解答 atcoder.jp 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fbabcs2035.hateblo.jp%2Fentry%2F2019%2F02%2F11%2F221709" title="AtCoder Beginner Contest 117：C - Streamline - きろく" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> https://cdn-ak.f.st-hatena.com/images/fotolife/b/babcs2035/20190211/20190211221650.png Hatena Blog https://hatena.blog 2019-02-11 22:17:09 rich https://babcs2035.hateblo.jp/entry/2019/02/11/221709 1.0 100%