hitoare https://blog.hatena.ne.jp/hitoare/ hitoare日記 https://hitoare.hatenablog.com/ 競技プログラミング AtCoder 企業コン 解説と異なる解法でした。 問題リンク atcoder.jp 問題概要 平面上にN個の集落があり、各集落iは座標\( (X_i,Y_i) \)にあって重み\(P_i\)が与えられている。 また、X軸とY軸には線路がある。 この時、X軸またはY軸に平行な線路をK本追加して、「重み×最も近い線路までの距離」の和Sを最小化したい。 最小値を\(K=0...N\)まで求めよ。 解法 線路は集落を通るように敷くのが最適なので、候補は実質2N本しかない。 片方の向きの敷き方を固定して、もう片方の向きの線路の敷き方はDPする。 集落はX座標の昇順にソートしておく。 X軸に平行な線路( \(y=Y_i\) )の… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fhitoare.hatenablog.com%2Fentry%2F2020%2F07%2F26%2F001515" title="E - M&#39;s Solution(M-SOLUTIONS プロコンオープン 2020) - hitoare日記" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2020-07-26 00:15:15 rich https://hitoare.hatenablog.com/entry/2020/07/26/001515 1.0 100%