ngtkana https://blog.hatena.ne.jp/ngtkana/ ブログ名 https://blog.ngtkana.com/ 問題 atcoder.jp 解説 行きと帰り（復元）があります。 行き まずは、コストが最小となるような、最後においたブロックの左端の X 座標の範囲を DP です。これはダブルヒープでシュミレーションができます。（※ この解説はダブルヒープで凸折れ線を扱うテクになれていることを仮定します。（はい？）） 帰り すると、最後のブロックを置くべき場所の範囲が決まりますから、適当に左端にでもおいておきましょう。すると、各ブロックについて 後ろのすでに場所を決めたブロックとの兼ねあいで、おいて良い場所 が順番に決まり、また、 前のこれから場所を決めるブロックを最適化したときにコストが最小になる区間 は… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fblog.ngtkana.com%2Fentry%2F2020%2F05%2F30%2F014836" title="ARC 070 E - NarrowRectangles 解説 - ブログ名" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> https://chart.apis.google.com/chart?cht=tx&chl=%20x_i Hatena Blog https://hatena.blog 2020-05-30 01:48:36 rich https://blog.ngtkana.com/entry/2020/05/30/014836 1.0 100%