C - Collision 2 Editorial by Nyaan
まず、競技プログラミングを始めたばかりの人は愚直に人を左右に動かしてシミュレーションすることを考えてしまうかもしれません。しかし、この問題では \(N \leq 2\times 10^5, x,y \leq 10^9\) と膨大な人数および空間での話をシミュレートしないといけないため、愚直なシミュレーションでは計算資源が到底足りません。
このような場合は、適切な考察によって高速な判定アルゴリズムを構成する必要があります。そのためには、まず「どのような条件の時に衝突が発生するか?」を定式化するのが大事です。これ無しでは適切なアルゴリズムを構成することができません。
さて、さっそく衝突が発生する必要十分条件を求めましょう。すると、適切な考察により、人 \(p\) と人 \(q\) が衝突する必要十分条件は次の通りとなります。
- 人 \(p\) と人 \(q\) の \(y\) 座標が同じである。
- 人 \(p\) の \(x\) 座標が 人 \(q\) より小さいならば、人 \(p\) は右を、人 \(q\) は左を向いている。(逆の場合は向きも逆になる。)
このように条件を言い換えることで、この問題は「上の条件を満たす人の組 \((p, q)\) が存在するか?」という問題に帰着することができました。よって for 文で \(p, q\) をすべて走査すれば解ける…と言いたいところですがこれでは \(\mathrm{O}(N^2)\) かかってしまい TLE するので更なる高速化が必要です。
もう少し考察を深めてみましょう。\(y\) 座標が同じ人たちを集めたとき、「この人たちの間に衝突が発生するのはどのような条件か?」というのを整理しましょう。するとこれは、
- (右を向いている人のうち一番左にいる人) と
- (左を向いている人のうち一番右にいる人)
が衝突するかどうか?が必要十分条件になっていることがわかります。言い換えると、 \(y\) 座標が同じ人からなる集合の中では、上の説明にある \(2\) 人以外は重要でない、ということです。
よって、次の \(2\) つの (キー, 値) を要素とする連想配列を持って適切計算していけば、衝突の有無を高速に判定できます。(詳細なアルゴリズムは実装例を参考にしてください。)
right_min
: キーを \(k\) としたとき、\(y=k\) でありかつ右を向いている人のうち最も \(x\) 座標が小さい人left_max
: キーを \(k\) としたとき、\(y=k\) でありかつ左を向いている人のうち最も \(x\) 座標が大きい人
計算量は \(\mathrm{O}(N)\) あるいは \(\mathrm{O}(N \log N)\) です。以下に Python での実装例を貼ります。
def Yes():
print("Yes")
exit(0)
N = int(input())
X, Y = [], []
for _ in range(N):
x, y = map(int, input().split())
X.append(x)
Y.append(y)
S = input()
right_min, left_max = dict(), dict()
for i in range(N):
if S[i] == 'R':
if Y[i] in left_max and X[i] < left_max[Y[i]]:
Yes()
else:
if Y[i] in right_min and right_min[Y[i]] < X[i]:
Yes()
if S[i] == 'R':
if Y[i] in right_min:
right_min[Y[i]] = min(X[i], right_min[Y[i]])
else:
right_min[Y[i]] = X[i]
else:
if Y[i] in left_max:
left_max[Y[i]] = max(X[i], left_max[Y[i]])
else:
left_max[Y[i]] = X[i]
print("No")
posted:
last update: