AtCoder Beginner Contest 130 F - Minimum Bounding Box

解法

各座標軸ごとに、動きのイメージをつかむ

時刻を文字 $t$ で表し、 $t$ に依存する変数を $x(t)$ のように表します。

まず、 $x, y$ 座標を分けて考えてみます。 $x$ 座標だけに注目すると、それぞれの点は以下の3つにグループ分けできます。

グループ1： $x$ 座標が時間あたり1ずつ増え続ける点（R）
グループ2： $x$ 座標が変わらない点（U、D）
グループ3： $x$ 座標が時間あたり1ずつ減り続ける点（L）

これらのグループそれぞれには点がたくさん含まれているかもしれませんが、そのうち座標の最大値と最小値だけを考えればよいことが分かります。求めたい答えに関わるのはこれら全ての座標の最大値 $x_{\max}(t)$ と最小値 $x_{\min}(t)$ であり、グループ内では相対的な位置関係が変わることはないからです。

そのため各グループは最小値から最大値までの区間と捉えることができて、動作のイメージは以下のようになります。もちろん位置関係がこの図のようになっているとは限りませんが、3つの区間がそれぞれ速度1, 0, -1で動いていると見なすことができます。

f:id:betrue12:20190617200007p:plain

最大・最小の入れ替わり点を考える

$x_{\max}(t)$ は3グループの最大値のうち最も大きいもの、 $x_{\min}(t)$ は同様に3グループの最小値のうち最も小さいものになります。これらの時間変化がどのようになっているか考えてみましょう。

3つの最大値のうちある値が最大値になっている間は、 $x_{\max}(t)$ は傾き-1, 0, 1のいずれかで変動します。そしてこの傾きが変わるのは、3点のうちどれが最も大きいかが入れ替わるときです。つまりこの時間変化は折れ線グラフになっています。

$x_{\min}(t)$ についても同様なので、 $x_{\max}(t) - x_{\min}(t)$ も折れ線グラフになります。そうすると何となく、この傾きが変わる時刻だけを候補として考えれば良いのでは？という仮説が立ちます。これらの時刻を「傾きが変わる」時刻と呼ぶことにしましょう。

これらの時刻は、異なるグループ間で最大値または最小値が同じ座標値になるような時刻と考えることができます。その組み合わせはそんなに多くないので、もしこれらの時刻だけを調べれば十分なのであれば、そのパターン数はとても少ないです。 $x, y$ 軸それぞれについてこのような時刻を列挙し、全探索しても十分間に合うでしょう。

この仮説が本当に正しいのか、もう少し細かく考えていきましょう。

本当に大丈夫？

ここまでは座標1軸だけで考えてきましたが、実際には2軸ありましたね。求めたいのは $(x_{\max}(t) - x_{\min}(t)) \times (y_{\max}(t) - y_{\min}(t))$ の最小値であり、この時間変化は折れ線グラフになるとは限りません。この式を $f(t)$ と置きましょう。

調べたいことは、先程の「傾きが変わる」時刻だけを調べれば十分かどうか。逆に言うと、 $x_{\max}(t), x_{\min}(t), y_{\max}(t), y_{\min}(t)$ の傾きがどれも変化しないような時刻 $t$ で $f(t)$ が最小値を取ることがあり得るかどうか？です。（ただし「傾きが変わる」時刻に挟まれた区間内の傾きがずっと0で、最小値を取り続けている場合は除きます）

結論を書いてしまうと、そのような場合は基本的には存在しないことが分かります。例外は「スタート時点である時刻0のときが最小値である」場合です。

このことを確かめていきましょう。時刻 $t$ における、 $x_{\max}(t) - x_{\min}(t)$ と $y_{\max}(t) - y_{\min}(t)$ の変化量の符号で場合分けします。それぞれの単位時間あたりの変化量を $dx, dy$ とします。

$dx \ge 0$ かつ $dy \ge 0$ の場合

このときは $f(x)$ は（広義）単調増加です。そのため途中の値で最小値を取ることはありません。

$dx \le 0$ かつ $dy \le 0$ の場合

このときは逆に $f(x)$ は（広義）単調減少です。そのため途中の値で最小値を取ることはありません。

$dx \lt 0$ かつ $dy \gt 0$ の場合、あるいはその逆

残ったのはこのケースです。このとき $f(t)$ はどうなるでしょうか。

どの値の傾きも変わらないような区間においては、 $x_{\max}(t) - x_{\min}(t)$ と $y_{\max}(t) - y_{\min}(t)$ はそれぞれ直線とみなせます。ここで $dx \lt 0$ かつ $dy \gt 0$ より、 $f(t)$ は正の実数 $a, c$ と実数 $b, d$ を用いて

$f(t) = (-at+b)(ct+d)$

と表すことができます。これは $t$ に関して放物線になり、2次の係数 $-ac$ が負であることから上に凸な放物線になります。そのため途中の値で極大値を取ることはありますが、最小値を取ることはありません。

以上の場合分けにより、 $f(t)$ の最小値を調べるには、 $x_{\max}(t), x_{\min}(t), y_{\max}(t), y_{\min}(t)$ のいずれかの「傾きが変わる」時刻だけを調べれば良いことが分かりました。これを全て列挙して全部試すと、答えを求めることができます。

※余談ですが、もしこの問題が「有限の時間だけ動かした場合の最大値を求めよ」という問題だったら、極大値を調べないといけないのでこのような解法は成り立ちませんね。

おまけ：実装をサボる

最後に実装についてちょっとしたテクを紹介します。先程まで説明してきたように、 $x, y$ 軸それぞれについて、各グループごとに最大値と最小値を出して、異なるグループのペアを全通り作って、それぞれの速度を考慮しながら最小値・最大値同士が交わる時刻を出して…と計算していくと確かに候補となる時刻を列挙できます。

ただ、場合分けが多くてちょっと面倒ですよね。もっと雑に集めることで、細かいことを気にしなくてもいいようにしましょう。

まず点たちを、LRUD の移動方向ごとに4つのグループに分けます。それぞれのグループから $x, y$ 軸それぞれについて最大値と最小値を出してきます。それらを $x, y$ 軸それぞれについてごちゃまぜに集めてしまい、 $X, Y$ とします。