pythonでAtCoder -ABC005-

対象

• AtCoder初心者（緑よりもランクが下の人）
• pythonがそれなりにかける人
• 数学やプログラミングに対する深い理解を持っていない人
  • Ex) DP, 深さ優先探索, メモ化再帰の実装ができない

動機

AtCoderは全ての問題に対して解説スライドが存在するが
解説をみて何となく理論を理解しても独力で実装ができない場合が多かった。

他の提出を見ても親切に解説コメントがついている回答はあまり存在せず、理解を実装に落とすことに苦労したため、簡単にでも解説がある回答はないものかと思い立ったことが動機である。

同様の苦労をしている人のためにも、稚拙なコードではあるが何らかの参考になればと思い
私の回答とそれに対する簡単なコメントを付与したコードをアップロードする。

実行環境

• python3

A

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

python3の割り算は切り捨てではなくfloatで行われるのでintにキャストする。
あるいは切り捨て除算演算子//を使う。

B

N = int(input())
print(min([int(input()) for _ in range(N)]))

pythonのfor文は遅いので高速化のためにリスト内包表記が用いられる場合がある。

C

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

flg = True
# 各お客さんに対し
for b in B:
    valid = []
    # 各たこ焼きに対し
    for i, a in enumerate(A):
        # 有効なたこ焼きがあれば、たこ焼きを取り除く
        if b - T <= a <= b:
            valid.append(a)
            A.pop(i)
            break
    # 有効なたこ焼きがなければ即終了
    if len(valid) == 0:
        flg = False
        break
print('yes' if flg else 'no')

D

# 入力を受け取る
N = int(input())
D = [list(map(int, input().split(' '))) for _ in range(N)]
Q = int(input())
P = [int(input()) for _ in range(Q)]

# 右下まで使う長方形を全通り列挙
S_BR = [[0] * N for _ in range(N)]
for i in range(N):
    for j in range(N):
        # 長方形の美味しさを計算
        for x in range(i, N):
            for y in range(j, N):
                S_BR[i][j] += D[x][y]

# 各長方形を全通り列挙
S = [0] * N * N
for i in range(N):
    for j in range(N):
        for x in range(i+1, N+1):
            for y in range(j+1, N+1):
                # 美味しさを計算
                # 左上起点の四角形 - 右上起点の四角形 - 左下起点の四角形 + 右下起点の四角形
                if y < N and x < N:
                    s = S_BR[i][j]-S_BR[i][y]-S_BR[x][j]+S_BR[x][y]
                elif y >= N and x >= N:
                    s = S_BR[i][j]
                elif y >= N:
                    s = S_BR[i][j]-S_BR[x][j]
                elif x >= N:
                    s = S_BR[i][j]-S_BR[i][y]
                else:
                    raise RuntimeError
                S[(x-i)*(y-j)-1] = max(S[(x-i)*(y-j)-1], s)

# nとn-1の美味しさを比べn-1の方が美味しい場合はnの美味しさを上書き
for i in range(1, len(S)):
    S[i] = max(S[i-1], S[i])

# 出力
[print(S[p-1]) for p in P]

素直に計算を行うとfor文のネストがものすごいことになり時間切れになってしまうので、四角形の内部の和を高速に求めるための工夫が必要。

右下を必ず含む長方形さえ計算してしまえばあとは組み合わせで表現ができることが肝。

終わりに

ざっくり説明でした。
ABC全問投稿を目指すのでよろしくお願いします。