対象
- AtCoder初心者（緑よりもランクが下の人、ABCのCD問題が解けない人）
- pythonがそれなりにかける人
- 数学やプログラミングに対する深い理解を持っていない人
- Ex) DP, 深さ優先探索, メモ化再帰の実装ができない
動機
AtCoderは全ての問題に対して解説が存在しますが
ざっくり説明を読んでわかった気になっても独力で実装ができないといった経験が多くありました。
参考のために他人の提出を見ても解説と綺麗にリンクした解答が簡単には見つからず
理解を実装に落とすことに苦労しました。
そこで、公式の解答とある程度リンクした実装を見ながら
アルゴリズムや数学的な理解とソースコードを紐付けたいと思ったことが本記事を寄稿した動機です。
いるかわかりませんが同様の苦労をしている人のためにも何らかの参考になればと思い
私の回答とそれに対する簡単なコメントを付与したコードを記載します。
実行環境
- python3
実装
凡例
実装時の事前情報を記します。
何も見ずに実装しているものは、コーディングが理想的でない可能性、アルゴリズムが理想的ではない可能性があります。
解説から実装しているものは、コーディングが理想的でない可能性があります。
実装
AB → 何も見ずに実装
CD → 解説を見て実装
A
A.py
S, T = map(int, input().split(' '))
print(T - S + 1)
B
B.py
from collections import defaultdict
N = int(input())
S = defaultdict(int)
for _ in range(N):
S[input()] += 1
print(max(S, key=S.get))
C
C.py
N = int(input())
C = [int(input()) for _ in range(N)]
p = 0
# 各コインに対し
for i in range(N):
# 自身の約数となっているコインの枚数を求める(自身のコインは除く)
S = [C[j] for j in range(N) if i != j and C[i] % C[j] == 0]
s = len(S)
# 自身のコインが、奇数枚目になる確率を求める
p += (s + 2) / (2 * s + 2) if s % 2 == 0 else 0.5
print(p)
期待値の特性を利用した解法です。
各コインの出現確率を求めていく発想にたどり着くことが難しいように感じます。
D
D.py
def calc(i, j, k, l):
if (i, j, k, l) in memo:
return memo[(i, j, k, l)]
res = 0
for X, Y in M:
# 計算したい領域に入っている機械のみを対象にする
if i < X <= k and j < Y <= l:
# この機械が取れる金塊
tmp = (k-i) + (l-j) - 1
# 左上、右上、左下、右下の領域で取れる金塊
tmp += calc(i, j, X-1, Y-1)
tmp += calc(X, j, k, Y-1)
tmp += calc(i, Y, X-1, l)
tmp += calc(X, Y, k, l)
res = max(res, tmp)
memo[(i, j, k, l)] = res
return res
W, H = map(int, input().split(' '))
N = int(input())
M = [tuple(map(int, input().split(' '))) for _ in range(N)]
memo = {}
print(calc(0, 0, W, H))
メモ化再帰を利用した解法を実装しています。
終わりに
今回はD問題はおろかC問題も解けませんでした。
体系的に学ぶために本買うべきですかね。。
以上です。