ABC393をPythonで（A～D、F）

AtCoder Beginner Contest 393の解答等の速報的まとめ

A問題

条件を満たすように答えを計算した

• 高橋君がfineのとき
  • 答えは３か４
• 青木君がfineのとき
  • 答えは２か４

A

s1, s2 = input().split()

ans = 1
if s1 == "fine":
    ans += 2
if s2 == "fine":
    ans += 1

print(ans)

B問題

可能性があるパターンを全て調べる

B

s = input()

ans = 0
for i in range(len(s)):
    if s[i] != "A":
        continue
    for j in range(i + 1, len(s)):
        if s[j] != "B":
            continue
        k = j * 2 - i
        if k < len(s) and s[k] == "C":
            ans += 1

print(ans)

C問題

始点と終点の組み合わせがすでに登場したものと一致するか$u_i = v_i$である辺の数を数える

C

n, m = map(int, input().split())
s = set()
ans = 0
for _ in range(m):
    e_i = tuple(sorted(map(int, input().split())))
    if e_i in s or e_i[0] == e_i[1]:
        ans += 1
    else:
        s.add(e_i)

print(ans)

D問題

外側の１から順番に内側へ移動させる

D

from collections import deque

n = int(input())
s = input()

d = deque([i for i in range(n) if s[i] == "1"])
ans = 0
cnt_front, cnt_back = 0, 0
while len(d) > 1:
    if cnt_front <= cnt_back:
        now = d.popleft()
        cnt_front += 1
        target = d[0]
        dist = target - now - 1
        ans += dist * cnt_front
    else:
        now = d.pop()
        cnt_back += 1
        target = d[-1]
        dist = now - target - 1
        ans += dist * cnt_front

print(ans)

E問題

まったくわからなかった

F問題

LISを求めるDPで、$i$番目まで実施したDPの各要素$dp_j$は長さが$j$の狭義単調部分列の最大値の下限である
よってクエリを$R_i$でソートしてDPをしながら答えを記録すればよい

F

from bisect import bisect_left, bisect

n, q = map(int, input().split())
a = list(map(int, input().split()))
query = [tuple(map(int, input().split())) for _ in range(q)]

d = dict()
for i, q_i in enumerate(query):
    if q_i not in d:
        d[q_i] = list()
    d[q_i].append(i)

lst = sorted(d.keys())
search = 0
ans = [0] * q
lis = []
for i, a_i in enumerate(a):
    ind = bisect_left(lis, a_i)
    if len(lis) <= ind:
        lis.append(a_i)
    else:
        lis[ind] = a_i
    while search < len(lst) and lst[search][0] == i + 1:
        ans_i = bisect(lis, lst[search][1])
        # print(ans_i)
        for s_i in d[lst[search]]:
            ans[s_i] = ans_i
        search += 1

for ans_i in ans:
    print(ans_i)