AtCoder Beginner Contest #005 復習

atcoder 復習 atcoder

はい。
http://abc005.contest.atcoder.jp

A - おいしいたこ焼きの作り方

Python2

x,y=map(int,raw_input().split())
print y/x

整数で求められる分だけが解になるので大体の言語でもおそらく余りは切り捨てになると思うのでy/xで終わると思う。

B - おいしいたこ焼きの食べ方

Python2

n=int(raw_input())
ans=101
for i in range(n):
    ans=min(ans,int(raw_input()))
print ans

多分まとめて受け取ってソートするか、常に最小値のみを保存するかだと思う。

C - おいしいたこ焼きの売り方

Python2

import heapq
 
t=int(raw_input())
n=int(raw_input())
a=map(int,raw_input().split())
m=int(raw_input())
b=map(int,raw_input().split())
ans=1
for i in b:
    while len(a):
        if a[0]+t<i:
            heapq.heappop(a)
        else:
            break
 
    if len(a)==0 or (a[0]<=i<=a[0]+t)==0:
        ans=0
        break
    heapq.heappop(a)
print ['no','yes'][ans]

for i in b でお客様がたこ焼きを取りに来て、古いたこ焼きは if a[0]+t<i の条件で判定して廃棄して、 a[0]<=i<=a[0]+t お客様と同時から+t秒以内のものはお渡し。お渡しできなければ即時終了でno。最後までお渡しできたらyes。お客様が来る基準？で処理しようとするときには古いたこ焼きの廃棄忘れがあると、新しいたこ焼きがあっても渡せなかった判定をしてしまったりするので注意。というか今回の解き直しではまりました。

D - おいしいたこ焼きの焼き方

Python2

n=int(raw_input())
dp=[0]*(n*n+1)
l=[]
 
 
for i in range(n):
    tmp=map(int,raw_input().split())
    dp[1]=max(dp[1],max(tmp))
    l.append(tmp)
b=[[0 for i in range(n)] for j in range(n)]
tmp=l[0][0]
b[0][0]=tmp
for i in range(1,n):
    b[0][i]=b[0][i-1]+l[0][i]
for i in range(1,n):
    b[i][0]=b[i-1][0]+l[i][0]
for i in range(1,n):
    for j in range(1,n):
        b[i][j]=b[i-1][j]+b[i][j-1]+l[i][j]-b[i-1][j-1]
 
q=int(raw_input())
chk=[]
for i in range(q):
    chk.append(int(raw_input()))
 
for i in range(n):
    for j in range(n):
        for y in range(i,n):
            for x in range(j,n):
                w=(y-i+1)*(x-j+1)
                if i==j==0:
                    dp[w]=max(dp[w],b[y][x])
                elif i==0:
                    dp[w]=max(dp[w],b[y][x]-b[y][j-1])
                elif j==0:
                    dp[w]=max(dp[w],b[y][x]-b[i-1][x])
                else:
                    dp[w]=max(dp[w],b[y][x]+b[i-1][j-1]-b[i-1][x]-b[y][j-1])
tmp=dp[1]
for i in range(1,n*n+1):
    dp[i]=tmp=max(tmp,dp[i])
for i in chk:
    print dp[i]

前回解こうとしたのが2年前くらいでその時は写経して、コードの内容も解説のよくわからないまま流してたけども、今回は解説や他のコードを見る前にAC出来たので多少は成長したのでしょう。
たこ焼き器のサイズNを受け取ると、店員が焼けるたこ焼きPの上限がN * Nに定まる。 そこで解答用の配列をN * N + 1の大きさで用意する。 たこ焼き器の情報を受取りつつ1マスの場合の最大値を確認した(後からも探索するし、1行ずつmaxを確認するのは効率いいのか不明)。 その後にN * N配列の中で累積和を求める。 その後に座標(i, j)の位置から座標(y, x)の範囲の美味しさ合計を先程の累積和を活用して求める。i, jからy, xの範囲の合計はy, xの位置の値からi-1, xの値とy, j-1の値を引いてi-1, j-1の値を加算したものである。i, jからy, xの範囲の値が確定したら解答用の配列の値と比較して大きい方を保存する。 端まで見終わったら入力例2のように４個焼くことができても３個しか焼かないほうが合計が大きくなる場合があるので解答用の配列を更新する。 そこまで終わったら解答用の配列からそれぞれ\(P_i\)番目の値を出力で解になる。