考察 (続きから)

  • (本番中は誤読をしていました。最小値の最小化だと思ってた)
  • (本番終了後に「交互にやればよい」というのをちらっと聞いた)
  • とりあえず $1$ 回だけの場合を考えたい。
  • Q. イチゴが置かれている位置の集合が与えられたときのケーキの美しさを求めるのはどうすればよいか？
  • A. 答えの二分探索をする。それぞれは貪欲に前回と同じ側に寄せる
  • 区間は $[0, L]$ でなくて $[-L/2, L/2]$ だと思った方が楽そう
  • 全体を反転させても同じなので、一番最初のは左側に振るとしてよい
  • $-x, +x \in [-L/2, L/2]$ に両方存在する場合はそこが壁になってそれぞれ独立に解ける
  • 貪欲の部分、本当に正しいですか？ 最後に合流が発生しちゃうとつらそう
  • 外側から決めていく感じで考えてたけど、内側からやればよさそう
  • 前回と同じ側に寄せる / 前回と違う側に寄せる では、常に後者の方がよい
  • Q. でも後々に影響しない？
  • A. しない。右 → 左 → 左 → 右 と使ったとき、最初の右と最後の右の距離は、途中の左と左の距離より大きい。つまり直近のふたつのみしか影響しない
  • 直近のふたつのみしか影響しないなら、左 → 右 → 左 のように交互に使うのが最適
  • これは $1$ 回の場合のみでなく、全体が解けた
  • 実装します
  • えーつまり、 std::multiset で $x \in [-L/2, 0]$ を持ってふたつ前とふたつ後ろとの差の最小値を管理する
  • 隣接 3 点をどんどん std::priority_queue に追加、取り出すときに妥当性判定するやつ
  • WA: 削除したときの場合を忘れてた
  • AC

解法

sorted な数列 $x = (x_0, x_1, \dots, x _ {k - 1})$ を考える。 位置 $A_i$ にイチゴが追加されるとき、数列に要素 $\min(A_i, L - A_i)$ が追加されるようにする。 このとき $b = \min_i x _ {i + 2} - x_i$ と $c = x _ {k - 1} - x _ {k - 2}$ の最小値 $\min(b, c)$ が答え。 std::multiset を使って $x$ を管理し、その要素が増減するたびに std::priority_queue に隣接 $3$ 項の組を追加する感じでやる。追加と削除が交互に来ると queue の中にごみが溜っていくが、最悪でも高々 $O(N)$ 要素なので気にしなくてよい。全体で $O(N \log N)$。

メモ

  • 隣接 $3$ 項間の演算をいい感じにできるライブラリがあるとよさそう (実装が重めなので)

リンク