betrue12 https://blog.hatena.ne.jp/betrue12/ ARMERIA https://betrue12.hateblo.jp/ AtCoder プログラミング 競技プログラミング I - Ramen 解説を見て通したけど、実装にけっこう手こずったので記録。 解法 距離の2乗をコストに持つDP、といえばCHTです（？）。CHT（Convex-Hull Trick）が使えるように、価格 の計算式を と変形します。 が についての一次式群から最小値を求める形式になっていて、CHTが使えそうです。 ただしこの問題の場合、CHTで解くには2つの課題があります。 店が開店する順番に価格を決定していく必要があるため の値を事前にソートできず、値を取得する点 にも追加する直線の傾き にも単調性がない。 店が閉まるという事象を扱わなければいけない。CHTの「直線を消す」という操作に相当す… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fbetrue12.hateblo.jp%2Fentry%2F2019%2F03%2F12%2F213215" title="早稲田大学プログラミングコンテスト2019 I - Ramen - ARMERIA" 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/betrue12/20190312/20190312212025.png Hatena Blog https://hatena.blog 2019-03-12 21:32:15 rich https://betrue12.hateblo.jp/entry/2019/03/12/213215 1.0 100%