ABC337をpythonで解く

A

　Xの和とYの和を求めて比較するだけ。

N=int(input())
XY=[list(map(int,input().split())) for _ in range (N)]
xwa=0
ywa=0
for X,Y in XY:
    xwa+=X; ywa+=Y
if xwa>ywa:
    print("Takahashi")
elif xwa<ywa:
    print("Aoki")
else:
    print("Draw")

B

　ABCの順になってる文字列はsortしても変わらないことを利用する。

S=input()
tame=[]
for i in S:
    tame.append(i)
tamesort=sorted(tame)
if tame==tamesort:
    print("Yes")
else:
    print("No")

C

　Aのindexと中身を入れ替えたAgyakuを作って前から順番に構成していく。

N=int(input())
A=list(map(lambda x:int(x)-1,input().split()))
Agyaku=[-1]*N
ans=[]
for i in range (N):
    if A[i]==-2:
        ans.append(i)
    else:
        Agyaku[A[i]]=i
for i in range (N-1):
    ans.append(Agyaku[ans[-1]])
for i in ans:
    print(i+1,end=" ")
print()

D

　厄介な問題だった。やっぱりABCのDは罠では？
　横に並べる場合と、縦に並べる場合とで独立して解析する。oが出来るだけ並んでいる場所を見つけたいが、途中でxが出てきたら無効化しないといけない。そこで、xが出てきたら-10**6を(実際には-K-1とかで十分)、oが出てきたら1を入れたリストを作り、これを前から1つずつ足していった総和リストを作る。
　総和リストのi+K番目からi番目を引いたものが負ならそれに対応する列(行)のi番目からi+K番目までのどこかにxがあることが分かり、非負ならoで並べることが可能でi番目からi+K番目までに含まれているoの総数がその値になっていることが分かる。
　xに対するアプローチと操作回数を最小にする位置がどこかを特定するアプローチを同時に行うのに発想が必要な問題だと感じた。

H,W,K=map(int,input().split())
S=[input() for _ in range (H)]
INF=-10**6
ans=[]
for i in range (H):
    hennka=[0]*W
    for j in range (W):
        if S[i][j]=="x":
            hennka[j]=INF
        elif S[i][j]=="o":
            hennka[j]+=1
    wa=[0]
    for j in hennka:
        wa.append(wa[-1]+j)
    for j in range (W-K+1):
        ans.append(wa[j+K]-wa[j])
for j in range (W):
    hennka=[0]*H
    for i in range (H):
        if S[i][j]=="x":
            hennka[i]=INF
        elif S[i][j]=="o":
            hennka[i]+=1
    wa=[0]
    for i in hennka:
        wa.append(wa[-1]+i)
    for i in range (H-K+1):
        ans.append(wa[i+K]-wa[i])
deka=max(ans)
if deka<0:
    print(-1)
else:
    print(max(0,K-deka))

E

　この手の問題は大体2進数で何とかしていく感じのことが多く、今回もそうでした。誰も毒を飲まなかったパターンも考慮すれば、N-1のbitlength人の友人で事足ります。友人1に2進数で表したときの1桁目が1のジュースを、友人2に2進数で表したときの2桁目が1のジュースを、……飲ませます。
　この結果、毒を飲んだ人が誰も現れないのはNが2の累乗である場合だけで、このときの毒入りジュースはNです。そうでない場合は、毒を飲んだ人のパターンから毒入りジュースの番号を特定できます。

N=int(input())
M=(N-1).bit_length()
print(M)
for i in range (M):
    iKA=[]
    for j in range (N+1):
        if (j>>i)&1==1:
            iKA.append(j)
    print(len(iKA),end=" ")
    for j in iKA:
        print(j,end=" ")
    print()
S=input()
ans=0
for i in range (M):
    if S[i]=="1":
        ans+=1<<i
if ans==0:
    print(N)
else:
    print(ans)

F

　問題見てない。

以下リンク
ABC336/ホーム/ABC338