ABC 139 F - Engines

• 問題
• AC (偏角ソート)
• AC (凸包)

偏角ソートして走査

$N$本のベクトル$v_1, ..., v_N$を任意に組み合わせて長さ最大のものを作る問題。偏角が$[\theta, \theta+\pi]$の区間に入っているベクトルは方向 $\theta + \pi / 2$への長さの増加に寄与するので、$v_1, ..., v_N$を偏角でソートしておいて、各区間$[\theta, \theta + \pi]$についてベクトルを加算して長さを比較すれば良い……のだけど、$\theta$は連続量なのでどの$\theta$を調べれば十分なのか考えなくてはならない。

以下、$v_1, ..., v_N$が既に偏角でソート済みとする。各$v_i$の偏角を基点にして$+ \pi$の範囲にあるベクトルを加算するという方針でだいたいは合っていそうだが、$(0, 10), (1, -1), (-1, -1)$のようなケースでうまくいっておらず、$(0, 10)$のみを使うパターンが漏れてしまう。$180\degree$の区間の両端がどのベクトルにも一致しないような、各偏角と偏角の「間」も基点として使う必要がある。

これを実現するには、各$v_i$の偏角に微小にプラスした地点から$+ \pi$の範囲までの走査も追加すれば良さそう。上の例で言うなら、$(1, -1)$の偏角に$0.000000001\degree$足したところから$+ 180 \degree$の範囲まで走査すれば、「間」のパターンを拾えている。ただ、実装にあたっては、いちいち微小な角度を足す必要はなく、$v_i$を基点にして$+ \pi$の範囲まで走査して$v_i + v_{i+1} + ... + v_k$というベクトルが得られたら、基点のベクトルを除いた$v_{i+1} + ... + v_k$も調べれば良い。

また、これだと各$v_i$から反時計回りの走査しかしていないので、時計周りにも調べる必要がある。各ベクトルの$x$成分をすべてマイナスに反転して鏡映にした上で、まったく同じ処理を適用するのが簡単だと思う。¹

計算量は、素朴に走査して${\mathcal O}(N^2)$。尺取り法っぽくやれば走査の部分はおそらく${\mathcal O}(N)$にできて、その場合はソートが律速で${\mathcal O}(N \log N)$。

---

コンテスト中は漏れるパターンの拾い方を詰められなくて、走査範囲を$\pi/2$から$\pi$まで雑に刻んで、通らなかったら乱択を加えるしかないと思っていたのだが、あっさり通ってしまった。偏角ソートしたら単に全区間をチェックすればよいということに気づけなかったのは反省。

凸包

原点のみの集合$P_0 := \{(0, 0)\}$からスタートして、与えられたベクトル$v_1, ..., v_N$によって移動可能な点を順に増やしていくとする:

$P_i := P_{i-1} \cup \{ p + v_i : p \in P_{i-1}\}$

$P_N$の点の中で原点からの距離がもっとも大きいものを求めればよい。

問題は$P_i$のサイズが指数的に増えることだが、凸包に含まれる頂点しか答えに影響しないので、毎回$P_i$の凸包を取ればよい。凸多角形とその平行移動の凸包を取ると、高々$2$しか頂点が増えないので、$P_i$のサイズが爆発しなくて済む。凸包が${\mathcal O}(N \log N)$で求まれば全体の計算量は${\mathcal O}(N^2 \log N)$。

---

1. 既存のテストケースだと反時計回りだけでも通るらしい。しかし、時計周りだけでは通らなかった。 ↩︎