Atcoder ABC243 振り返り

　約8ヶ月ぶりの緑パフォが出ました．レートが＋30以上上がったのもその時ぶり……これを続けて入緑できるよう頑張ります．

A - Shampoo【AC】

　V<=10^5なので愚直にシミュレーションしても間に合います．

V, A, B, C = map(int, input().split())
x = [A, B, C]
f = ["F", "M", "T"]
count = 0
while V >= 0:
    V -= x[count % 3]
    count += 1
count -= 1
print(f[count % 3])

B - Hit and Blow【AC】

　2．の時，N<=1000なので，計算量O(N)のinを使ってAi=Bjを調べても間に合います．

N = int(input())
A = [int(i) for i in input().split()]
B = [int(i) for i in input().split()]

one = 0
two = 0

for i in range(N):
    if A[i] == B[i]:
        one += 1
    elif A[i] in B:
        two += 1
print(one)
print(two) 

C - Collision 2【AC】

　人は真横にしか動かないので，yが同じ人同士で衝突判定を行い、全ての人が居るyで衝突が無かったら衝突無し，どこか一つのyでも衝突があれば衝突ありとします．
　同じyの人についてLに進むグループとRに進むグループに分けます．このとき衝突無しとなるパターンは以下の画像の3つです．

　左2つのパターンの判定は簡単です．LグループRグループで0人となるグループがあれば左2つのパターンのどちらかになります．
　右のパターンはLRグループどちらにも人がいます．これの判定は，max(Lグループのx座標)＜min(Rグループのx座標)が成り立つときです．逆にこれが成り立たないとき必ず衝突します．

N = int(input())

tizu = {}

for i in range(N):
    x, y = map(int, input().split())
    tizu.setdefault(y, [])
    tizu[y].append([i, x])

S = input()

for j in tizu.values():
    L = []
    R = []
    for i, x in j:
        if S[i] == "L":
            L.append(x)
        else:
            R.append(x)
    L.sort()
    R.sort()
    if len(R) > 0 and len(L) > 0 and R[0] < L[-1]:
        print("Yes")
        break
else:
    print("No")

D - Moves on Binary Tree【AC】

　愚直にURLに合わせて，X//=2やX*=2，X=2*X + 1としていたらTLEになります．恐らく計算の途中でXが64ビットを超えてしまいpypyの処理が遅くなるからです．
　このため数字では無く文字列として計算することを考えます．今いる頂点Xを二進数で表すと，完全二分目で左の子に移動する事は，Xに0を付け足すのと同義になります．同様に，右の子に移動する事は，Xに1を付け足すのと同義になります．これは，左の子は2i，右の子は2i+1であるからです．そして親に移動する事は末項の数字を削除すれば良いです．
　このリストは，勿論64個を超えても処理が遅くなることはないので高速に動きます．

N, X = map(int, input().split())
S = input()

ans = list(bin(X)[2:])


for s in S:
    if s == "U":
        ans.pop()
    elif s == "L":
        ans.append("0")
    else:
        ans.append("1")

print(int("".join(ans), 2))