第一回日本最強プログラマー学生選手権決勝 C - Maximize Minimum

お題箱より。同じ問題に2件リクエストがありました。

簡潔に飛ばし気味ではあるものの公式解説の説明が分かりやすいと思うので、流れは公式解説に沿いつつ図や行間を補って書いていきます。

解法

イチゴの最適な折り返し方

まずクエリについては忘れます。「ケーキを左半分と右半分で鏡写しのように見たときに、イチゴを何回でも反対側に折り返していいので、一番近いイチゴ間の距離をできるだけ遠くしてください」という問題です。

何回でも折り返していいので、まずは左半分の側に全てのイチゴをまとめて、それからいくつかのイチゴを選んで折り返す最適な選び方を考えてみましょう。イチゴの個数を $k$ として、左側に全てまとめたときのイチゴの座標を小さい方から $b_{0}, b_{1}, ..., b_{k-1}$ とします。ここで $b_{i} \le \frac{L}{2}$ です。

まず簡単なケースから考えましょう。以下のようにイチゴが間隔1で等間隔に並んでいて、ケーキが十分長いようなケースです。

f:id:betrue12:20191009231447p:plain

このときの最適な並べ方は、 $b_{1}, b_{3}, b_{5}, ...$ のイチゴを折り返すことです。つまり座標の小さいものから左右交互に配置していきます。

f:id:betrue12:20191009231505p:plain

こうすることで一番近い距離が2になります。もし交互になっていないところがあると距離1が登場してしまうので、これが最適です。

この「全部片側に寄せて、座標の小さいものから左右交互」という考え方を実は一般化できて、このような置き方が常に最適になります。そのときのイチゴ間の距離は、 $b_{0}, b_{1}, ..., b_{k-1}$ を用いると

1つ飛ばしでのイチゴの距離 $b_{2}-b_{0}, b_{3}-b_{1}, ..., b_{n-1} - b_{n-3}$
最も右側（ケーキの中心）に近い2つのイチゴを、左右逆側に配置した時の距離 $L - b_{n-1} - b_{n-2}$

になります（2.を忘れがちなので注意ですね）。これらのうち最も小さい値が答えになります。

最適性の証明は公式解説の通りです。連続する3つのイチゴ $b_{i}, b_{i+1}, b_{i+2}$ を考えると、これらのうちどれか2個のペアは左右同じ側に置かないといけないので、 $b_{i+1}-b_{i}, b_{i+2}-b_{i+1}, b_{i+2}-b_{i}$ の少なくとも1つはイチゴ間の距離として採用しないといけません。それならば、この中で一番大きい $b_{i+2}-b_{i}$ を常に採用する左右交互の並べ方が最適ということになります。

2.の最も右側のイチゴ2つを左右同じ側ではなく左右逆側に配置したほうが常に得であることも、逆側に配置したときの距離 $L - b_{n-1} - b_{n-2}$ と同じ側に配置した時の距離 $b_{n-1} - b_{n-2}$ の大小を評価すれば分かります。（ $b_{i} \le \frac{L}{2}$ であることを使います）

クエリの処理を考える

ではクエリの処理方法を考えます。

まずは各クエリでイチゴを入れるのか除くのか判断するため、今あるイチゴの「元の」座標を管理する集合1を作ります。

それとは別に、折り返した座標である $b_{0}, b_{1}, ..., b_{k-1}$ を管理できる集合2を作ります。鏡写しで同じ座標にイチゴが2個あることもあるので、多重集合のほうが適しています。

各クエリでは集合1を使って要素を出すのか入れるのか判断し、集合1, 2に要素を出し入れします。そして答えを求めるために「1つ飛ばしでのイチゴの距離」のうち最も小さいものを求める必要があります。これは以下のようにして求めることができます。

集合2を順序付き多重集合（C++の multiset など）として持ち、常に要素がソートされているようにします。そうすると要素を1個挿入または削除したときには、「1つ飛ばしでのイチゴの距離」はその周囲でだけ変化します。具体的には当該要素の左側2つ・右側2つまでの座標だけ分かれば、変化する値は以下のように計算できます。

f:id:betrue12:20191009232547p:plain

つまり1回のクエリは、「その時点での "1つ飛ばしでのイチゴの距離" たちの集合」に対する高々5個の要素の出し入れとして処理できます。これも multiset として管理しておけば、各操作の後にその最小値を求めることができます。

multiset において「ある要素の2つ左の要素」などを求めるには、いったん lower_bound などでその要素の場所を求めた後にイテレータ操作をすれば良いです。順序付き集合が標準で存在しない言語の場合は、自前の平衡二分探索木を使うか座標圧縮＋セグメント木＋二分探索などの処理が必要になると思われます…。

これで1つ飛ばしでのイチゴの距離の最小値が分かります。また集合2の大きいほうから2要素を見ることで $L - x_{n-1} - x_{n-2}$ も計算できます。これで各クエリに $O(\log N)$ で答えることができて間に合います。