ABC421をPythonで（A～D+α）

AtCoder Beginner Contest 421の解答等の速報的まとめ

A問題

辞書に突っ込んで確認

A

n = int(input())

d = dict()
for i in range(n):
    s = input()
    d[i + 1] = s

x, y = input().split()
x = int(x)
print("Yes" if x in d and d[x] == y else "No")

B問題

問題文通りのコードを書く

B

lst = list(map(int, input().split()))

while len(lst) < 10:
   a_1, a_2 = lst[-1], lst[-2]
   lst.append(int(str(a_1 + a_2)[::-1]))

print(lst[-1])

C問題

$ABAB...$ か $BABA...$ しか条件を満たすパターンはない
また、$A$を適切な場所に移動させれば$B$は勝手に正しい場所に移っている
よって$A$を$AB$パターンにする手数と$BA$パターンにする手数を比較する

C

n = int(input())
s = input()

lst = list()
for i, s_i in enumerate(s):
    if s_i == "A":
        lst.append(i)

AB = 0
BA = 0
for i, l_i in enumerate(lst):
    AB += abs(l_i - i * 2)
    BA += abs(l_i - (i * 2 + 1))

print(min(AB, BA))

D問題

まず、一方が方向転換するタイミングでクエリを分ける
その後、以下の交差パターンに当たるか調べる

1. 同じ地点から同じ方向に動く
2. 逆向きに動いて同じ場所を踏む（偶奇の一致が必要）
3. 経路が交差かつ交点までの距離が一致

D

def move(arr_i, x, y, arr_j, a, b, distance):
    d_i, d_j = arr[arr_i]
    x += d_i * distance
    y += d_j * distance

    d_a, d_b = arr[arr_j]
    a += d_a * distance
    b += d_b * distance

    return x, y, a, b

# 引用：https://tjkendev.github.io/procon-library/python/geometry/segment_line_intersection.html
# 線分同士の交点判定
def dot3(O, A, B):
    ox, oy = O; ax, ay = A; bx, by = B
    return (ax - ox) * (bx - ox) + (ay - oy) * (by - oy)
def cross3(O, A, B):
    ox, oy = O; ax, ay = A; bx, by = B
    return (ax - ox) * (by - oy) - (bx - ox) * (ay - oy)
def dist2(A, B):
    ax, ay = A; bx, by = B
    return (ax - bx) ** 2 + (ay - by) ** 2
def is_intersection(P0, P1, Q0, Q1):
    C0 = cross3(P0, P1, Q0)
    C1 = cross3(P0, P1, Q1)
    D0 = cross3(Q0, Q1, P0)
    D1 = cross3(Q0, Q1, P1)
    if C0 == C1 == 0:
        E0 = dot3(P0, P1, Q0)
        E1 = dot3(P0, P1, Q1)
        if not E0 < E1:
            E0, E1 = E1, E0
        return E0 <= dist2(P0, P1) and 0 <= E1
    return C0 * C1 <= 0 and D0 * D1 <= 0



arr = {'U':(-1, 0), 'D':(1, 0), 'L':(0, -1), 'R':(0, 1)}

xt, yt, xa, ya = map(int, input().split())
n, m, l = map(int, input().split())
s = [list(input().split()) for _ in range(m)]
t = [list(input().split()) for _ in range(l)]

lst = list()
last_s, last_t = 0, 0
arr_s, arr_t = "", ""
ind_s, ind_t = 0, 0
while True:
    if last_s == 0:
        if len(s) <= ind_s:
            break
        arr_s, last_s = s[ind_s]
        last_s = int(last_s)
        ind_s += 1
    if last_t == 0:
        arr_t, last_t = t[ind_t]
        last_t = int(last_t)
        ind_t += 1

    diff = min(last_s, last_t)
    lst.append((arr_s, arr_t, diff))
    last_s -= diff
    last_t -= diff

ans = 0
for arr_t, arr_a, diff in lst:
    if (xt, yt) == (xa, ya):
        if arr_t == arr_a:
            ans += diff
        xt, yt, xa, ya = move(arr_t, xt, yt, arr_a, xa, ya, diff)
    else:
        nxt_xt, nxt_yt, nxt_xa, nxt_ya = move(arr_t, xt, yt, arr_a, xa, ya, diff)
        if (arr_t in "LR" and arr_a in "DU") or (arr_t in "DU" and arr_a in "LR"):
            if is_intersection((xt, yt), (nxt_xt, nxt_yt), (xa, ya), (nxt_xa, nxt_ya)) and (xt, yt) != (xa, ya):
                if abs(yt - ya) == abs(xt - xa):
                    ans += 1
        elif {arr_t, arr_a} == {"L", "R"} and yt % 2 == ya % 2:
            if is_intersection((xt, yt), (nxt_xt, nxt_yt), (xa, ya), (nxt_xa, nxt_ya)) and (xt, yt) != (xa, ya):
                ans += 1
        elif {arr_t, arr_a} == {"U", "D"} and xt % 2 == xa % 2:
            if is_intersection((xt, yt), (nxt_xt, nxt_yt), (xa, ya), (nxt_xa, nxt_ya)) and (xt, yt) != (xa, ya):
                ans += 1

        xt, yt, xa, ya = nxt_xt, nxt_yt, nxt_xa, nxt_ya

print(ans)

F問題

本番の思考
連結リストで管理すればいい→TLEするがそのパターンがわからない

TLEとなるのは

• 0,1,2,3,4,... のときに2,3と入力があって3から検索

を繰り返したとき

この対策で、$x$から検索と$y$から検索を同時並行で行えばトータルの検索回数を$O(q)$に抑えられる

F

def search(target, target2, a):
    res1 = 0
    res2 = 0
    now_1 = target
    now_2 = target2
    while True:
        now_1 = a[now_1]
        now_2 = a[now_2]
        if now_1 == target2:
            return res1, 1
        elif now_2 == target:
            return res2, 2
        else:
            res1 += now_1
            res2 += now_2

def main():
    A = [-1] * (5 * 10 ** 5 + 10)
    for i in range(1, int(input()) + 1):
        com = list(map(int, input().split()))
        if com[0] == 1:
            x = com[1]
            nxt = A[x]
            A[x] = i
            A[i] = nxt
        else:
            x, y = com[1:]
            res, t = search(x, y, A)
            if t == 1:
                A[x] = y
            else:
                A[y] = x
            print(res)

if __name__ == '__main__':
    main()