ABC338をpythonで解く

　問題文は問題 - AtCoder Beginner Contest 338を参照してください。

A

　S[0]が小文字ならNo出してexit()、S[1:]に大文字があったらNo出してexit()、両方通過したらYes。大文字か小文字かはisupper()、islower()で判定できます。

S=input()
if S[0].islower():
    print("No")
    exit()
for i in S[1:]:
    if i.isupper():
        print("No")
        exit()
print("Yes")

B

　それぞれの文字が何個あるかをcountに貯めると、max(count)に達しているindexの中で一番小さなindexが示す文字が答えとなる。

S=input()
count=[0]*26
for i in S:
    count[ord(i)-ord("a")]+=1
ooi=max(count)
for i in range (26):
    if count[i]==ooi:
        print(chr(ord("a")+i))
        exit()

C

　Aを作る量を減らしていけば、Bを作れる量は必ず単調増加していくのでそれを利用して、尺取り法？みたいな感じで調べれば大して時間を使わずに調べられる。

N=int(input())
Q=list(map(int,input().split()))
A=list(map(int,input().split()))
B=list(map(int,input().split()))
deka=10**7
Adeka=-2
for i in range (deka):
    for j in range (N):
        if A[j]*i>Q[j]:
            Adeka=i-1
            break
    if Adeka!=-2:
        break
ans=[0]
Bnow=0
for i in range (Adeka,-1,-1):
    for j in range (Bnow,deka):
        hanntei=-2
        for k in range (N):
            if A[k]*i+B[k]*j>Q[k]:
                hanntei=j-1
                break
        if hanntei!=-2:
            break
    Bnow=hanntei
    ans.append(i+Bnow)
print(max(ans))

D

　どの橋を落とした場合についてもすべて調べたいが、愚直にやると時間がかかりすぎます。注目すべきは、1ターン移動したとき、増える長さは2パターンしかないことです。変化量だけ貯めて、後で和を出して評価すれば高速にすべての場合について調べられます。
　以下のように記述しました。dpのようなやつを真っ先に思いつきますが、O(NM)になって死ぬので、hennkaに貯めて最後に足していることが分かります。

N,M=map(int,input().split())
X=list(map(lambda x:int(x)-1,input().split()))
hennka=[0]*(N)
#dp=[0]*N
for i in range (M-1):
    sita=min(X[i],X[i+1])
    ue=max(X[i],X[i+1])
    junn=ue-sita
    gyaku=N-junn
    #dp[0～sita-1]+=junn
    #dp[sita～ue-1]+=gyaku
    #dp[ue～N-1]+=junn
    hennka[0]+=junn
    hennka[sita]-=junn
    hennka[sita]+=gyaku
    hennka[ue]-=gyaku
    hennka[ue]+=junn
ans=[0]*(N+1)
for i in range (N):
    ans[i+1]=ans[i]+hennka[i]
print(min(ans[1:]))

E

　考えてみると、確実にまず隣同士で繋がってるやつがないと無理だと分かり、それを取り除くとまた隣同士で繋がっているやつがないとダメ……となっている。なのでトポロジカルソート的な要領で調べれば出来そうだなぁ、と思った。

以下リンク
ABC337/ホーム/ABC339