anta1 https://blog.hatena.ne.jp/anta1/ antaの競技プログラミング練習日記 https://anta1.hatenadiary.org/ SRM 二分探索 問題 Editorial 問題 数列initialが与えられる。 これの各々を移動させて、等差数列の並び替えにしたい。ただしそれぞれの数値は重複があってはいけない。 移動させるのに移動させた分だけコストがかかる。 コストを最小化せよ 2 -2*10^9 解答 Editorialを見た。 まず、数列をソートできる。 そうすると、等差数列の順序はそのままの順序でよくなる。 次に、どれかの数1つはそのままの位置で良い。 そうすると、コストは等差の関数(d => Σ |v[fixed] + d * (j - fixed) - v[j]|)になる。 そしてこの関数は凸である。何故ならば、Sumの各項は凸… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fanta1.hatenadiary.org%2Fentry%2F20130213%2F1360740878" title="SRM 281 DIV1 Hard Equidistance - antaの競技プログラミング練習日記" 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 2013-02-13 16:34:38 rich https://anta1.hatenadiary.org/entry/20130213/1360740878 1.0 100%