AGC025-C(700) Interval Game
概要
数直線があり、最初に高橋くんは0にいる。青木くんは、N(<= 10^5)この閉区間を持っていて、次のようなことをN回行える。
N回の操作後、高橋君は数直線の0にもどる。
青木君が最適な行動をした際に、高橋君を最大でどれぐらい移動させることができるか？
ACするまで
1. いい感じに左右左右と往復させたいなぁ。
2. 左端まで行く区間を相対的に右において、右端まで行く区間を相対的に左に置けばよさそう。
3. 指定する区間はできるだけ右往左往させるようにしたい。そのため、できるだけならば毎回方向転換させるような指定方法をしたい。
4. 3ができる前提で考えると、容易に最適が求まるが、そのままでは右におく区間と左におく区間の数の差は1以内(この制約下でのみ、あまらず右往左往可能)と、条件が厳しい。
5. 方向転換を必要としない区間は、実は省いてもよい。右往左往の時のベストはよりお互いに離れてるモノから行き来させるので、その間にそういう転換を必要としない区間を使ったことにすれば実質無視できるという算段。これで実質的に区間の数の差が1以内はいらなくなる。
6. お互いにより離れてる区間から右往左往させる。これの終点は、右に属する区間の左端 < 左に属する区間の右端、を満たす、つまり両側に属する区間が交わった瞬間が終点。
7. これをまとめるて実装、AC。
考察
この問題は、最善行動はいい感じに左右に右往左往させることであることは簡単な実験からわかる。
ひとまず面倒な制約を考えずに、右側において、区間の左端に高橋君を行かせたいもの(以下A)と左側において、区間の右端に高橋君を行かせたいもの(以下B)に分けてみる。これをいい感じに振り分ければ、最適であるとわかる。この時の答えは、以下の図からもわかる通り、
{(Aに属するものの左端の和) - (Bに属するものの右端の和)} * 2
さて、問題はいかにして区間を左右に振り分けるのだが、上の例のようにきれいに振り分けられるのならばそれでいい。しかし、ほとんどの例では、すべての区間を(Aの左端 > Bの右端)を満たすように振り分けができない。AとBの所属要素がそれぞれは絶対に交わるというのをどう対処すればいいのか。
この問題の最善は右往左往であるが、その理由としては、区間Xの後に方向転換させずに区間X+1を移動させるという行動では、区間Xの意味がないからである。
ここで、最適化問題の典型テクニック(僕談)、
都合の悪い要素を、操作順序を工夫するするなどで消せる場合がある。
を思い出す。
この問題の場合、都合の悪い要素とは、右往左往の邪魔となる、きれいに左と右に振り分けできない区間たちである。AとBに振り分けるとき、お互いに一番離れてるAとBの所属区間から始めれば、その2つの区間に行く途中に、それらの右往左往の邪魔となる区間を使ったことにすればよい。(一番離れてるA or Bに行くにあたって、それ以外の区間をいくつ使おうが、A or Bへいく距離は変わらない)
これで、実質的にいい感じに複数回、区間を左右に振り分けて右往左往させればいいとわかる。
AとBはより互いに離れてる区間同士から右往左往を始めれば、AとBの所属区間が交わる瞬間まで答えに加算して、交わったのならばそれより先の区間は右往左往に邪魔だとみなして、さきほどの論理で無視できる。
これは、左端を降順でソートして、右端を昇順でソートしたのち、左端の大きい順にAに振り分け、右端の小さい順にBに振り分ける。この際、一度同じ区間がAかつBに振り分けられるという可能性を考えるが、同じ区間内では左端(A) < 右端(B)、が成り立ち、これはAとBの所属区間が交わらないに反してるので、そもそも考えなくてよい。
実装する際には、実質的な右往左往回数が偶数ならば先ほどの図のように対応するA or Bの区間があるが、奇数は最後にはない。実装法にもよるが、[0, 0]という区間を追加しておけば、奇数時に終了条件の「AとBの所属集合が交わったら」の手前で、0を最後の奇数番目のペアとすれば、0に戻るようにすることができる。(これは実装法によっては不要なテクニックかもしれない)
ACソースコード：
Submission #8700359 - AtCoder Grand Contest 025
簡略化させたACソースコード：
Submission #8700722 - AtCoder Grand Contest 025
一言
俺は確実に強くなってる！（自己暗示）
