ABC338をPythonで（A～E）

AtCoder Beginner Contest 338

A問題

isupperとislowerを使って確かめる

A

s = input()
if s[0].isupper() and (len(s) <= 1 or s[1:].islower()):
    print("Yes")
else:
    print("No")

B問題

問題文の通りに調べる

B

s = input()
lst = [0] * 26
for s_i in s:
    lst[ord(s_i) - ord("a")] += 1

print(chr(ord("a") + lst.index(max(lst))))

C問題

料理の種類が１つだけだったら割れば簡単に求まる
よって、０からaだけで考えた時の上限値までの全通りで残った材料でbを作れる数を計算して
aの数とbの数の和の最大値が答え

C

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

ans = 0
limit = min(q[i] // a[i] for i in range(n) if a[i] > 0)
for x in range(limit + 1):
    y = 10 ** 9
    for i in range(n):
        if b[i] == 0:
            continue
        elif q[i] < a[i] * x:
            y = - 10 ** 9
        else:
            y = min(y, (q[i] - a[i] * x) // b[i])

    ans = max(ans, x + y)

print(ans)

D問題

累積和
$x_i$と$x_{i+1}$の間の橋を壊した時の長さと、そうではないほうを壊した時の長さを累積和を使ってうまいこと計算する（下式参照）

D

n, m = map(int, input().split())
x = list(map(lambda x:int(x) - 1, input().split()))

dist = [0] * n
for now, to in zip(x, x[1:]):
    dist[min(now, to)] += n - abs(now - to)
    dist[max(now, to)] -= n - abs(now - to)
    
    if min(now, to) > 0:
        dist[0] += abs(now - to)
        dist[min(now, to)] -=  abs(now - to)
    if max(now, to) < n:
        dist[max(now, to)] +=  abs(now - to)
    
for i in range(n - 1):
    dist[i + 1] += dist[i]

print(min(dist))

E問題

メモ化再帰を使って

1. $(a,b)$間に$a,b$の外側とつながっている組はないか
2. もし間どおしで繋がっている組$(x, y)$があったらそのペアで調べる
3. 次に$y+1$を調べる（2へ）

再帰上限に気を付けて実装する

E

from sys import setrecursionlimit

setrecursionlimit(10 ** 7)

n = int(input())
data = [list(map(lambda x:int(x) - 1, input().split())) for _ in range(n)]

p = [0] * (2 * n)
for a, b in data:
    p[a] = b
    p[b] = a

memo = [False] * (2 * n)
def check(a, b):
    global memo
    if memo[a]:
        return
    else:
        memo[a] = True
        memo[b] = True
        now = a + 1
        while now < b:
            if p[now] < a or b < p[now]:
                exit(print("Yes"))
            elif now < p[now]:
                check(now, p[now])
                now = p[now]
            now += 1


for i in range(2 * n):
    if i < p[i]:
        check(i, p[i])

print("No")