ABC454をPythonで（A～E）

キーサイト・テクノロジープログラミングコンテスト（AtCoder Beginner Contest 454）の解答等の速報的まとめ

A問題

そのまま

A

l, r = map(int, input().split())
print(r - l + 1)

B問題

セットを使って比較する

B

n, m = map(int, input().split())
f = list(map(int, input().split()))
s = len(set(f))
print("Yes" if s == n else "No")
print("Yes" if s == m else "No")

C問題

有効グラフでたどれる頂点を調べる

C

from collections import deque

n, m = map(int, input().split())
edge = [list() for _ in range(n)]
for _ in range(m):
    u, v = map(int, input().split())
    edge[u - 1].append(v - 1)

check = set()
q = deque()
q.append(0)

while q:
    now = q.popleft()
    if now in check:
        continue
    check.add(now)
    for to in edge[now]:
        if to not in check:
            q.append(to)

print(len(check))

D問題

$A,B$両方から括弧をとれるだけ取った形が一致するか調べる
取るときはスタックを利用して逐次調べる
ただ全部入れるとTLEしたので2つ入れないで調べる

D

def func(s):
    lst = list()
    one, two = "", ""
    for s_i in s:
        if s_i == ")" and one == two == "x" and lst and lst[-1] == "(":
            lst.pop()
        else:
            if one != "":
                lst.append(one)
            one = two
            two = s_i

    if one != "":
        lst.append(one)
    if two != "":
        lst.append(two)

    return lst

for _ in range(int(input())):
    a = input()
    b = input()
    print("Yes" if func(a) == func(b) else "No")

E問題

できるのは$N$が偶数かつ$A+B$が奇数の時

できるときは
$A$列にかかるまで端まで行って折り返す
$A$列あたりでジグザグに移動
そのあとはゴールまで折り返しを繰り返す

E

for _ in range(int(input())):
    n, a, b = map(int, input().split())
    if n % 2 == 1 or (a + b) % 2 == 0:
        print("No")
    else:
        x, y = 1, 1
        ans = list()
        while not (x == a or x + 1 == a):
            ans.append("R" * (n - 1))
            ans.append("D")
            ans.append("L" * (n - 1))
            ans.append("D")
            x += 2

        to_x = x + 1

        while not(x == to_x and y == n):
            if x == to_x:
                if (x - 1, y) == (a, b):
                    ans.append("R")
                    y += 1
                else:
                    ans.append("UR")
                    x -= 1
                    y += 1
            else:
                if (x + 1, y) == (a, b):
                    ans.append("R")
                    y += 1
                else:
                    ans.append("D")
                    x += 1
                    if y < n:
                        ans.append("R")
                        y += 1

        while (x, y) != (n, n):
            ans.append("D")
            ans.append("L" * (n - 1))
            ans.append("D")
            ans.append("R" * (n - 1))
            x += 2

        print("Yes")
        print("".join(ans))