「アルゴリズム」一覧

問題 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 日に取れる...

問題 B - Frog 2 回答 動的計画法を使って解く。 TLEで間に合わなかった回答 in, k = map(int, input().split()) h = # dpの最小値を変更する関数 def chmin(a, b): if...

ABC004 Dを動的計画法で解きたい -> 動的計画法って何？ -> accoderに動的計画法のコンテストがある！　という順番です。 DPとはDynamic Programming、動的計画法の略です。 動的計画法（どうてきけいかくほう、英:...