LoginSignup
0
0

ABC333をPythonで(A~E)

Posted at

トヨタ自動車プログラミングコンテスト2023#8(AtCoder Beginner Contest 333)

A問題

A
n = input()
print(n * int(n))

B問題

距離のパターンが2パターンだけだから、
それぞれどちらのパターンか調べればいい

B
s = input()
t = input()
def near(s):
    s1, s2 = s
    return {s1, s2} == {"A", "E"} or abs(ord(s1) - ord(s2)) == 1

print("Yes" if near(s) == near(t) else "No")

C問題

解答例の最後が最大値なので、それ以下を全部出力して$N$番目を出力すればいい

C
n = int(input())

lst = set()
for i in range(1, 13):
    for j in range(i, 13):
        for k in range(j, 13):
            lst.add(int("1" * i) + int("1" * j) + int("1" * k))

ans = sorted(lst)
print(ans[n - 1])

D問題

$1$と他をつないでいる辺を除いたグラフの中で1つの木以外を取り除いたときに$1$が葉になる
よって答えは$N-max($各木のサイズ$)$となる

D
from sys import setrecursionlimit

setrecursionlimit(10 ** 7)
from collections import defaultdict

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)]


n = int(input())
UF = UnionFind(n)
child = []
for _ in range(n - 1):
    u, v = map(lambda x:int(x) - 1, input().split())
    if u == 0:
        child.append(v)
    else:
        UF.union(u, v)

ans = n + 1
if len(child) <= 1:
    print(1)
else:
    for i in child:
        ans = min(ans, n - UF.size(i))
    print(ans)

E問題

各ポーション獲得時にそれを取らないと倒せないモンスターが出てくる時だけ拾えばいい
それを調べるために出来事を逆順に見ていって

  1. ポーションの時は、それを使って倒すべきモンスターがいるときだけ拾い、必要ポーション数を$-1$する
  2. モンスターの時は、それを倒すのに必要ポーション数を$+1$する
E
n = int(input())
query = [list(map(int, input().split())) for _ in range(n)]
d = {0:0}
lst = []
for t, x in query[::-1]:
    if t == 1:
        if x in d and d[x] > 0:
            lst.append(1)
            d[x] -= 1
        else:
            lst.append(0)
    else:
        if x not in d:
            d[x] = 0
        d[x] += 1

if max(d.values()) > 0:
    print(-1)
else:
    lst = lst[::-1]
    ans = cnt = ind = 0
    for t, _ in query:
        if t == 1:
            if lst[ind] == 1:
                cnt += 1
            ind += 1
        else:
            cnt -= 1
        ans = max(ans, cnt)

    print(ans)
    print(*lst)
0
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
0
0