ABC243

コンテスト参加

atcoder.jp

とりあえずA問題、B問題の2完できた。C問題、D問題は壁が厚く終わったあとに解説見ながら取り組んだ。

C問題

1. Y座標が同じ
2. 人 p は右を、人 q は左を向いている
3. 人 p の x 座標が 人 q より小さい ときのみ衝突が起こる

さらに右を向いている人のうち最も左のx座標にいる人、左を向いている人のうち最も右のx座標にいる人のみ見ればよい。

1.、2.の条件は気づけたが、3.の条件で

R (2, 1)、L (1, 1)
のようなY座標が同じかつRLだが衝突しないケースを考慮できていなかった・・・。

D問題

解説を見て二分木の性質を思い出して実装したがTLEになり解けない。

list[-1] でリストの最後から数えた要素を取得できることを知った

これだとTLEになる

    for i in range(N):
        if S[i] == "U" and len(T) > 0 and (S[i - 1] == "L" or S[i - 1] == "R"):
            T.pop()
        else:
            T.append(S[i])

こっちだとOK

    for i in range(N):
        if S[i] == "U" and len(T) > 0 and (T[-1] == "L" or T[-1] == "R"):
            T.pop()
        else:
            T.append(S[i])

今の心境