ABC-372

A

$URL\:\to$ https://atcoder.jp/contests/abc372/tasks/abc372_a

#置換

def solve():
    s = String().trans({".":""})
    print(s)

    return 0

解法

’.’ を ” に置換するだけ。

---

B

$URL\:\to$ https://atcoder.jp/contests/abc372/tasks/abc372_b

#数学

def solve():
    m = Integer().content
    l = IntegerList().content
    while m>0:
        i=0
        while m>=3**i: i+=1
        l.append(i-1)
        m -= 3**(i-1)
    print(len(l))
    print(*(l))

    return 0

解法

$m > 3^n$ を満たす最大の $n$ を求めて $m = m - 3^n$ を $m = 0$ になるまで続ける。

---

C

$URL\:\to$ https://atcoder.jp/contests/abc372/tasks/abc372_c

#視点の発想

def check(string, x):
    ct = 0
    for i in range(3):
        if string[x+i-2:x+i+1]==["A","B","C"]: ct += 1
    return ct

def solve():
    n,q = Integer().content
    s = Word().content
    cnt = 0

    for i in range(n-2):
        if s[i]=="A" and s[i+1]=="B" and s[i+2]=="C": cnt += 1

    for _ in range(q):
        x,c = StringList().content
        x = int(x)
        before = check(s, x-1)
        s[x-1] = c
        after = check(s, x-1)
        print(cnt := cnt + after - before)

    return 0

解法

1クエリで1文字変更される -> せいぜい ABC の変わる数は $-3$ ~ $3$ 個なので、その変更されるところの差分を求める。

要するに、 $X_i$ が先頭、真ん中、最後の $3$ パターンを検査して、差分を求める。

---

D

$URL\:\to$ https://atcoder.jp/contests/abc372/tasks/abc372_d

#stack

def solve():
    n = Integer().content
    h = IntegerList().content
    ans = [0]*n
    stack = []

    for i in range(-1, -n , -1):
        while stack and stack[-1] < h[i]:
            stack.pop()
        stack.append(h[i])
        ans[i-1] = len(stack)

    print(*ans)

    return 0

解法

後ろから見たときに $i$ 番目の解では $i+1$ ~ $N$ 番目のビルが対象となる。 $i$ 番目の解を求めるとき、$h_x<h_{y}\ (i+1 \le x \lt y)$ が成り立つもののみをスタックに入れるとよい。そして、$Stack_{top}$ $\lt$ $h_{i+1}$ になるまでpopし続け、条件を満たす、もしくはスタックが空になったらpushする。 がここで、後ろから見ることで(stackの特徴的に)効率的に見ることができる。

---