読者です 読者をやめる 読者になる 読者になる

AOJ0516: Maximum Sum(累積和, しゃくとり法)

Maximum Sum | Aizu Online Judge 累積和としゃくとり法を知らなかったのでメモ。計算量を考えずに全探索までしていたので書いておく。 最悪 O(n2) で最大 n = 100000 だから全探索はダメ(指数記号が出せない…)。

AOJ0030: Sum of Integers 

Sum of Integers | Aizu Online Judge 深さ優先探索の問題。C++ で書いたものを Python に翻訳して分かった気になるアレ。 #!/usr/bin/env python def dfs(pos, t, sum): global cnt if t == n: if sum == s: cnt += 1 return if pos > 9: return dfs(pos+1,…