No Caffeine, No Life

プログラミング(主にPython)

動的計画法

ABC 054 D:Mixing Experiment 動的計画法

問題: D: Mixing Experiment - AtCoder Beginner Contest 054 | AtCoder 解説: editorialにあるように、変数やdp tableを設定してみる。 (3重リストを用いている) 解答例:

ABC 054 C:One-stroke Path 動的計画法 メモ化再帰 ビットdp

問題: C: One-stroke Path - AtCoder Beginner Contest 054 | AtCoder 解説: 頂点の数がとても少ないので、頂点の数におけるすべての順列において、すべての点をたどることができるかを深さ優先探索(dfs)で探っていく。 1番目の例は、 ある点と点がつなが…

AOJ ALDS1_10_C:最長共通部分列 (LCS: Longest Common Subsequence)  動的計画法

問題: 最長共通部分列 | アルゴリズムとデータ構造 | Aizu Online Judge 解説: 「普通の」アルゴリズムはこちら: 最長共通部分列問題 (Longest Common Subsequence) - naoyaのはてなダイアリー が、下記にあるように、最長共通部分列の「長さ」だけを求め…

AOJ DPL_1_E:編集距離 Levenshtein Distance

問題: Edit Distance (Levenshtein Distance) | Aizu Online Judge 解説: いまさら編集距離 (Levenshtein Distance) を実装するぜ | takuti.me こんなふうにわかりやすく書けるなんてすごいなぁ…。 解答例: 上記そのままですが…。 ちなみに、pythonにはLe…

AOJ DPL_1_C:ナップザック問題 (同じ種類の品物はいくつでも選ぶことができる場合) 動的計画法

問題: Knapsack Problem | Aizu Online Judge 解説: 最もシンプルな場合と同じように、 :種類の品物を用いて大きさのナップザックに入れる場合の価値の最大値 :品物の価値と重さのリスト と置いたとき、は、 の、最大値で決まる。(この3点目が、重複を…

AOJ DPL_1_B:ナップザック問題 動的計画法

問題: ナップザック問題 | 動的計画法 | Aizu Online Judge 解説: :種類の品物を用いて大きさのナップザックに入れる場合の価値の最大値 :品物の価値と重さのリスト と置いたとき、は、 の、最大値で決まる。 解答例:

AOJ DPL_3_B:最大長方形 (Largest Rectangle) 動的計画法

問題: 最大長方形 | 動的計画法 | Aizu Online Judge 解説: 与えられた盤面に対し、 「(縦に見て)連続してきれいなマス目が何個並んでいるか」をカウント。それを「ヒストグラム」とみなして、 ヒストグラムに内接する最大の長方形を割り出す という具合…

AOJ DPL_3_A:最大正方形(Largest Square) 動的計画法

問題: 最大正方形 | 動的計画法 | Aizu Online Judge 解説: :位置から見て、左上に向かってできる最大の正方形の数 このように設定したとき、は、左上( )、左( )、上( )から決定される。すなわち、左上、左、上の要素の最小値+1となる: 解答例:

ABC 060 D:Simple Knapsack 全探索(直積集合)、動的計画法(メモ化再帰)

問題: D: Simple Knapsack - AtCoder Beginner Contest 060 | AtCoder 解説: 問題の解説にあるように、今回は重さの範囲が限定されている(w0 <= wi <= w0+3)ので、それを考慮すると全探索することができる。すなわち、 重さは全部で4通り。 その4通りに…