「Python」一覧

問題 J - Sushi 期待値DP 期待値DPについて以下分かりやすいです。 確率 DP を極めよう また、Pythonであるということ以外、メモ化再帰は以下のほぼ写経です。 Educational DP Contest の F ～ J...

問題 I - Coins 確率DPの問題。 参考資料 確率 DP を極めよう 回答 TLEだった回答 PyPyではAC。 import sys # input処理を高速化する input = sys.stdin.readli...

問題 H - Grid 1 DP、数え上げ問題。 回答 import sys # input処理を高速化する input = sys.stdin.readline def main(): # input H, W = map(int,...

問題 G - Longest Path 有向非巡回グラフであり、DP の更新順序が非自明な問題です。 メモ化再帰を使うか、トポロジカルソートを使います。 解き方は以下を参考にしています。 Educational DP Contest の F ～ J...

問題 F - LCS 最長共通部分列問題です。 最長共通部分列問題については、以下の解説がとても分かりやすいです。 Common Subsequence 解説 最長共通部分列問題 (Longest Common Subsequence) 回答...

問題 E - Knapsack 2 回答 TLEで間に合わない最初の回答 アルゴリズム的には合っているかな？ import sys # input処理を高速化する input = sys.stdin.readline # 入力 N, W = ...

問題 D - Knapsack 1D - Knapsack 1 回答 最初にTLEで間に合わなかった回答 考え方としては合っているはず…。 import sys # inputを高速化する。 input = sys.stdin.readline ...

問題 C - Vacation 回答 動的計画法を使って解く。 貰うDP ノード i への遷移方法を考える。 つまり、 dp の値がわかっているときに、dp の値を更新する。 ただし、i - 1日に取った行動が i 日に取れる...