ABC382をPythonで（A～D,F）

AtCoder プログラミングコンテスト2024（AtCoder Beginner Contest 382）の解答等の速報的まとめ

https://atcoder.jp/contests/abc382



# A問題
https://atcoder.jp/contests/abc382/tasks/abc382_a

ドットの個数とクッキーを食べる日数の和が答え
```python:A
n, d = map(int, input().split())
print(input().count(".") + d)
```
# B問題
https://atcoder.jp/contests/abc382/tasks/abc382_b

スタックを利用してインデックスが大きいほうからクッキーを食べていく
```python:B
n, d = map(int, input().split())
s = input()

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

for _ in range(d):
    if stack:
        stack.pop()

ans = ["."] * n
for i in stack:
    ans[i] = "@"

print("".join(ans))
```
# C問題
https://atcoder.jp/contests/abc382/tasks/abc382_c

寿司の美味しさが大きいほうから$A$の先頭から食べるかどうかを順に試していく
```python:C
n, m = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

lst = [(b_i, i) for i, b_i in enumerate(b)]
lst.sort(reverse=True)

ans = [-1] * m
ind = 0
for i, a_i in enumerate(a, 1):
    while ind < m and lst[ind][0] >= a_i:
        ans[lst[ind][1]] = i
        ind += 1

for ans_i in ans:
    print(ans_i)
```
# D問題
https://atcoder.jp/contests/abc382/tasks/abc382_d

dfsで答えの数列を生成していく
各項の上限に気を付けて回す
```python:D
def dfs():
    global lst
    if len(lst) == n:
        ans.append(lst.copy())
    elif len(lst) == 0:
        for i in range(1, 11):
            lst.append(i)
            dfs()
            lst.pop()
    else:
        key = lst[-1]
        maxi = m - 10 * (n - len(lst) - 1)
        for i in range(key + 10, maxi + 1):
            lst.append(i)
            dfs()
            lst.pop()


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

ans = list()
lst = list()
dfs()

print(len(ans))
for a_i in ans:
    print(*a_i)
```
# E問題
分からん

# F問題
https://atcoder.jp/contests/abc382/tasks/abc382_f

区間更新区間最小値取得の遅延セグ木を使う
セグ木は[yaketake08’s 実装メモ](https://tjkendev.github.io/procon-library/python/range_query/rmq_ruq_segment_tree_lp.html)から引用
```python:F
class RMQ_and_RUQ:
    def __init__(self, N):
        self.INF = 2 ** 31 - 1
        
        self.LV = (N - 1).bit_length()
        self.N0 = 2 ** self.LV
        self.data = [self.INF] * (2 * self.N0)
        self.lazy = [None] * (2 * self.N0)
        
    
    # 伝搬対象の区間を求める
    def gindex(self, l, r):
        L = (l + self.N0) >> 1
        R = (r + self.N0) >> 1
        lc = 0 if l & 1 else (L & -L).bit_length()
        rc = 0 if r & 1 else (R & -R).bit_length()
        for i in range(self.LV):
            if rc <= i:
                yield R
            if L < R and lc <= i:
                yield L
            L >>= 1
            R >>= 1
    
    
    # 遅延伝搬処理
    def propagates(self, *ids):
        for i in reversed(ids):
            v = self.lazy[i - 1]
            if v is None:
                continue
            self.lazy[2 * i - 1] = self.data[2 * i - 1] = self.lazy[2 * i] = self.data[2 * i] = v
            self.lazy[i - 1] = None
    
    
    # 区間[l, r)をxで更新
    def update(self, l, r, x):
        *ids, = self.gindex(l, r)
        self.propagates(*ids)
    
        L = self.N0 + l
        R = self.N0 + r
        while L < R:
            if R & 1:
                R -= 1
                self.lazy[R - 1] = self.data[R - 1] = x
            if L & 1:
                self.lazy[L - 1] = self.data[L - 1] = x
                L += 1
            L >>= 1
            R >>= 1
        for i in ids:
            self.data[i - 1] = min(self.data[2 * i - 1], self.data[2 * i])
    
    
    # 区間[l, r)内の最小値を求める
    def query(self, l, r):
        self.propagates(*self.gindex(l, r))
        L = self.N0 + l
        R = self.N0 + r
    
        s = self.INF
        while L < R:
            if R & 1:
                R -= 1
                s = min(s, self.data[R - 1])
            if L & 1:
                s = min(s, self.data[L - 1])
                L += 1
            L >>= 1
            R >>= 1
        return s


h, w, n = map(int, input().split())
data = list()
for i in range(n):
    r, c, l = map(int, input().split())
    data.append([r, c, i, l])

data.sort(reverse=True)
tree = RMQ_and_RUQ(w + 10)
ans = [0] * n
for r, c, i, l in data:
    s = tree.query(c, c + l)
    if s >= tree.INF:
        ans[i] = h
        tree.update(c, c + l, h)
    else:
        ans[i] = s - 1
        tree.update(c, c + l, s - 1)

for ans_i in ans:
    print(ans_i)
```