ABC05CとD問題

問題はhttp://abc005.contest.atcoder.jp/

C問題

解答の方針

たこやき（A)、お客さん（B)ともに、最後列から参照する。
AとBの時間の差が許容時間（T)以下の時,AとBともに次のものを参照する。
許容時間以上の時、Aのみを参照する。
先に、Bの最後まで見たとき、Yesを返し、Aを最後まで見たときはNoを返す。

コード

abc05c.py

T = int(input())
N = int(input())
A = list(map(int,input().split()))
M = int(input())
B = list(map(int,input().split()))

def dfs(i,j):
    global T
　　###先にAがなくなったらno,Bがなくなったらyes###
    if j == -1:
        return 'yes'
    if i == -1:
        return 'no'

    if B[j]-A[i] <= T and 0 <= B[j]-A[i]:
        return dfs(i-1,j-1)    
    else:
        return dfs(i-1,j)

res = dfs(N-1,M-1)
print(res)

D問題

解答の方針

すごくわからなかったので解説を見た
だいたい3つの処理に分けられる。

1.右下から始まる長方形の面積をN*N行列にいれる,
Nから0までを参照するので、
i*jの長方形を求めるときは、D[i][j] +　[i+1][j]の長方形 + [i][j+1]の長方形 + [i+1][j+1]の長方形を計算することで、計算量がN*Nですむ
dp[i][j]にi*jの面積をいれる

2.1からN*Nまでのそれぞれの面積でたこ焼きの値が最大のものを探す。
0からNまで参照する
　i*jの長方形を参照し、(i<=k<=N),(j<=l<=N)までの、長方形k*jと長方形i*lまでを引き、長方形k*lを足してやることで、右下から始まらない長方形でのおいしさを求め、
　(i-k)*(j-l)にて、長方形の面積の計算を行い、面積ごとのおいしさの最大値を格納する

3.面積ごとのおいしさの最大値をまとめた配列を、その面積以下のなかでおいしさの最大値をまとめた配列に更新する。

コード

abc05d.py

N = int(input())
D = []
for i in range(N):
    D.append(list(map(int,input().split())))
Q = int(input())
P = []
for i in range(Q):
    P.append(int(input()))

dp = [[0 for i in range(N+1)] for i in range(N+1)]  #N+1*N+1とることでdp[N][N]を求めやすくする

###右下から始まる長方形の面積を求める###
for i in range(N)[::-1]:
    for j in range(N)[::-1]:
        dp[i][j] = dp[i + 1][j] + dp[i][j + 1] - dp[i + 1][j + 1] + D[i][j]#Nから0まで下りていくので,i+1はひとつ前のものを参照している。

res = [0 for i in range(N**2 + 1)]

###最大値の探索###
for i in range(N):
    for j in range(N):
        for k in range(i+1,N+1):#iの値より右にある座標を参照
            for l in range(j+1,N+1):#jより下の座標を参照
                s = (k-i)*(l-j)
                res[s] = max(res[s],dp[i][j] - dp[k][j] - dp[i][l] + dp[k][l])

###最大値の更新###
for i in range(1,len(res)):
    res[i] = max(res[i-1],res[i])

for i in P:
    print(res[i])