AtCoder Beginner Contest 129
はい。
https://atcoder.jp/contests/abc129
oooo-x レーティングはC問題の入力不備で確定が後になるので。。。 無駄にWAはなし、最近やや安定してるっぽいかな。
A - Airplane
PyPy3
l=[int(i) for i in input().split()] l.sort() print(l[0]+l[1])
小さい数2つの和で出してましたが、3つの総和から最大値を引くという方法があるようです。その方が賢くて楽そうですね。。
B - Balance
PyPy3
n=int(input()) w=[int(i) for i in input().split()] d=[0]*n for i in range(n): d[i]=d[i-1]+w[i] ans=chk=d[-1] for i in range(n-1): ans=min(ans,abs(d[-1]-d[i]-d[i])) print(ans)
左からの累積和を用意しておいて1つずつずらしながら差の絶対値が最大となるものを探す。
C - Typical Stairs
PyPy3
mod=1000000007 n,m=map(int,input().split()) d=set([]) w=[0]*(n+2) for i in range(m): a=int(input()) d.add(a) for i in range(n): if i==0 and 1 not in d: w[1]=1 elif i==0 and 1 in d: w[1]=0 if i==0 and 2 not in d: w[2]=1 elif i==0 and 2 in d: w[2]=0 if i>0: if i+1 not in d: w[i+1]=(w[i+1]+w[i])%mod if i+2 not in d: w[i+2]=w[i] print(w[-2]%mod)
無駄に長いです。移動をもっと単純な更新で求められるようです。DPとか練習しましょう。
D - Lamp
PyPy3
def sol(): h,w=map(int,input().split()) l=[] x=[[0]*w for i in range(h)] y=[[0]*w for i in range(h)] for i in range(h): s=input() l.append(s) for i in range(h): for j in range(w): if j==0 and l[i][j]==".": x[i][j]=1 elif l[i][j]==".": x[i][j]=x[i][j-1]+1 for i in range(h): for j in range(1,w): t=-1*(j+1) if l[i][t]==".": x[i][t]=max(x[i][t],x[i][t+1]) for i in range(w): for j in range(h): if j==0 and l[j][i]==".": y[j][i]=1 elif l[j][i]==".": y[j][i]=y[j-1][i]+1 for i in range(w): for j in range(1,h): t=-1*(j+1) if l[t][i]==".": y[t][i]=max(y[t][i],y[t+1][i]) ans=chk=0 for i in range(h): for j in range(w): ans=max(ans,x[i][j]+y[i][j]-1) print(ans) if __name__=="__main__": sol()
縦と横をそれぞれ照らせる範囲を調べておいて、座標(i,j)の時に縦+横-1で最大となる箇所が解だと思います。解説では上下左右で4方向で〜という方針っぽいです。PyPy3ではAC人数そこそこいるけどPython3では少ないのがtwitterで話題になっているようです。どうでもいいですね。