ABC341をPythonで（A～F）

トヨタ自動車プログラミングコンテスト2024#2（AtCoder Beginner Contest 341）の解答等のまとめ

A問題

「10」を入力された数だけ繰り返し「1」を付け足す

A

print("10"*int(input())+"1")

B問題

順番に計算していく

B

n = int(input())
a = list(map(int, input().split()))

for i in range(n - 1):
    s, t = map(int, input().split())
    a[i + 1] += a[i] // s * t

print(a[-1])

C問題

$(0, 0)$スタートとして通る場所を計算しておいて、あとは全探索

計算量的に$O(HWM) >10 ^ 8$だから間に合わさそうと思ったけど通った

C

h, w, n = map(int, input().split())
t = input()
s = [input() for _ in range(h)]

array = {"L":(0, -1),"R":(0, 1),"U":(-1, 0),"D":(1, 0)}
path = {(0, 0)}
x, y = 0, 0
for t_i in t:
    x += array[t_i][0]
    y += array[t_i][1]
    path.add((x, y))
path = list(path)

ans = 0
for i in range(h):
    for j in range(w):
        if s[i][j] == "#":
            continue
        if all(0 <= i + x < h and 0 <= j + y < w and s[i + x][j + y] == "." for x, y in path):
            ans += 1

print(ans)

D問題

二分探索

D

from math import lcm

n, m, k = map(int, input().split())

L = lcm(n, m)

ok, ng = 10 ** 20, 0
while abs(ok - ng) > 1:
    mid = (ok + ng) // 2
    if mid // n + mid // m - mid // L * 2 >= k:
        ok = mid
    else:
        ng = mid

print(ok)

E問題

クエリ1で反転させたとき影響を受けるところが$[L-1,L],[R,R+1]$の2か所の間だけ
よって区間取得できるセグ木を使って

1. 同じものが連続するところはFalse、しないところはTrueに
2. 範囲内がすべてTrueだったらYesを答える。そうでないならNo

となるように設定する

E

class SegTree:
    # single update & range get
    def __init__(self, n, ide_ele, seg_func):
        self.n = n
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.tree = [ide_ele] * 2 * self.num
        self.seg_func = seg_func

    def init_value(self, values):
        for i in range(self.n):
            self.tree[self.num + i] = values[i]
        for i in range(self.num - 1, 0, -1):
            self.tree[i] = self.seg_func(self.tree[2 * i], self.tree[2 * i + 1])

    def update(self, k, x):
        """
        k番目の値をxに更新
        k: index(0-index)
        x: update value
        """
        k += self.num
        self.tree[k] = x
        while k > 1:
            self.tree[k >> 1] = self.seg_func(self.tree[k], self.tree[k ^ 1])
            k >>= 1

    def query(self, l, r):
        """
        [L, r)のseg_funcしたものを得る
        L: index(0-index)
        r: index(0-index)
        """
        res = self.ide_ele

        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                res = self.seg_func(res, self.tree[l])
                l += 1
            if r & 1:
                res = self.seg_func(res, self.tree[r - 1])
            l >>= 1
            r >>= 1
        return res


n, q = map(int, input().split())
s = input()
tree = SegTree(n, True, lambda x, y: x and y)

for i in range(n - 1):
    if s[i] == s[i + 1]:
        tree.update(i, False)

for _ in range(q):
    com, L, R = map(lambda x:int(x) - 1, input().split())
    if com == 0:
        if L > 0:
            tree.update(L - 1, tree.query(L - 1, L) ^ True)
        tree.update(R, tree.query(R, R + 1) ^ True)
    else:
        print("Yes" if tree.query(L, R) else "No")

F問題

各マスに1つ駒があったときに最大何手稼げるかが調べられれば$a_i$と掛けた和が答えになる
それを調べるには$w_i$の値が小さいほうからDPで調べればいい。なぜなら

1. $w_i$が小さい頂点へしか遷移できない
2. 遷移する頂点が稼げる手数がわかっているなら、ナップサック問題のようにしてとけるから

F

n, m = map(int, input().split())

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

w = list(map(int, input().split()))
a = list(map(int, input().split()))

count = [0] * n
lst = [(w_i, i) for i, w_i in enumerate(w)]
for w_i, now in sorted(lst):
    dp = [0] * w_i
    dp[0] = 1
    for to in edge[now]:
        if w[to] < w_i:
            for i in range(w_i - 1, -1, -1):
                if i - w[to] < 0: break
                dp[i] = max(dp[i], dp[i - w[to]] + count[to])
    count[now] = max(dp)

ans = sum(count[i] * a[i] for i in range(n))
print(ans)