LoginSignup
1
0

ABC335をPythonで(A~E)

Posted at

AtCoder Beginner Contest 335(Sponsored by Mynavi)

A問題

末尾を落として、$4$を付け加える

A
print(input()[:-1] + "4")

B問題

起きうる全通りを試して$N$以下だったら出力する

B
n = int(input())
for i in range(n + 1):
    for j in range(n + 1):
        for k in range(n + 1):
            if i + j + k <= n:
                print(i, j, k)

C問題

1の点が$(n, 0)$から$(1,0)$まで移動した後クエリに従って移動したとみなすと、
2番目の点は1手前の1の座標で、3番目の点は2手前の1の座標で...$a$番目の点は$a-1$手前の1の座標だから

スタックにその移動を追加していき、答えるときは後ろから$p$番目を答えればよい

C
n, q = map(int, input().split())

lst = [(i + 1, 0) for i in range(n)][::-1]
arr = {"U":[0, 1], "D":[0, -1], "R":[1, 0], "L":[-1, 0]}

for i in range(q):
    com, x = input().split()
    if com == "1":
        lst.append((lst[-1][0] + arr[x][0], lst[-1][1] + arr[x][1]))
    else:
        print(*lst[-int(x)])

D問題

渦巻き状に数字を書いていけばいい

D
n = int(input())

lst = [[""] * n for _ in range(n)]
x, y, arr = 0, 0, 0
array = [[1, 0], [0, 1], [-1, 0], [0, -1]]

for i in range(n ** 2 - 1):
    lst[x][y] = i + 1
    if not(0 <= x + array[arr][0] < n and 0 <= y + array[arr][1] < n) or lst[x + array[arr][0]][ y + array[arr][1]] != "":
        arr = (arr + 1) % 4
    x, y = x + array[arr][0], y + array[arr][1]

lst[x][y] = "T"

for l_i in lst:
    print(*l_i)

E問題

まず、$A$の値が小さくなる方向へは考える必要がない
$A$の値が同じときはUnionFindで同じ頂点だとして扱えばいい

あとはトポロジカルソートの要領で各UnionFindの代表点を探索すればいい

E
from collections import defaultdict, deque


class UnionFind:
    """
    URL : https://note.nkmk.me/python-union-find/
    """
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)


n, m = map(int, input().split())
a = list(map(int, input().split()))
data = [list(map(lambda x:int(x) - 1, input().split())) for _ in range(m)]

UF = UnionFind(n)
for u, v in data:
    if a[u] == a[v]:
        UF.union(u, v)

edge = [[] for _ in range(n)]
cnt = [0] * n
for u, v in data:
    u_i, v_i = UF.find(u), UF.find(v)
    if a[u_i] < a[v_i]:
        edge[u_i].append(v_i)
        cnt[v_i] += 1
    elif a[u_i] > a[v_i]:
        edge[v_i].append(u_i)
        cnt[u_i] += 1


INF = 10 ** 10
dist = [-INF] * n
q = deque()
for i, c_i in enumerate(cnt):
    if c_i == 0:
        q.append(i)
    if UF.same(0, i):
        dist[i] = 1

while q:
    now = q.popleft()
    for to in edge[now]:
        dist[to] = max(dist[to], dist[now] + 1)
        cnt[to] -= 1
        if cnt[to] == 0:
            q.append(to)

ans = dist[UF.find(n - 1)]
print(ans if ans > 0 else 0)
1
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
1
0