ABC243C

ABC243C の解説

atcoder.jp

解答コード 

https://atcoder.jp/contests/abc243/submissions/30091837

問題

2次元平面座標で，同じy座標を移動する点同士が衝突するかどうかを判定する問題です．

解説

いつも通り，無言で投下する概要図です．

ABC243C_overview

点はx方向にしか移動できないので，y座標の値が異なれば衝突しません．
このことから，同じy座標の値の点同士を評価すれば良いことがわかります．

では，同じY座標同士をまずグループ化します．
yの制約が10^9 なので，その分だけ配列を作成するのは，合理的ではありません．
これを実現する方法は２つあると思います．
1) 最初にyでソートする．
2) 辞書型でまとめる     <- 今回はこっち

今から，Y座標ごとに点をまとめます．
このとき，その点が「L向きなのかR向きなのか」もまとめてあげるとスッキリします．すなわち，座標と向き（L or R）を同時に処理します．

上記の内容を実現するために，一旦標準入力を全部読み取ります．

N = int(input())
coords = [list(map(int, input().split())) for _ in range(N)]
S = input()

収納するためのdict と向きを定義します．向きを定義した意味は後程わかります．

Y = {}
d = {'R': 0, 'L': 1}

それでは，あらかじめ読み取っておいた標準入力を順番に処理していきます．
各y座標の値ごとに長さ2の二次元配列を用意して，
index=0にR向きのx座標を
index=1にL向きのx座標を入れます．

for i in range(N):
    x, y = coords[i]
    drct = d[S[i]]
    if y not in Y:
        Y[y] = [[], []]  # [[x Right], [x Left]]
    Y[y][drct].append(x)

最後に，各y座標ごとに
R向きでx座標が最小の点と，L向きでx座標が最大の点が衝突できるかを
大小関係をもとに判断します．

ans = 'No'
for r, l in Y.values():
    if l and r:
        r_min = min(r)
        l_max = max(l)
        if r_min < l_max:
            ans = 'Yes'
            break
print(ans)

以上，ABC243Cの解法でした．

＜参考解説リンク＞