AtCoder [AtCoder][DP][Educational DP Contest][競プロ]J-Sushi
Educational DP Contest
問題
問題キャプチャ
方針
\(dp\)として、\(i\)は\(a_i = 1\)の個数、\(j\)は\(a_i = 2\)の個数、\(k\)は\(a_...
DP
AtCoder 
AtCoder [AtCoder][DP][競プロ][Educational DP Contest]I-Coins
Educational DP Contest
問題
問題キャプチャ
方針
表の枚数が\(i\)枚である確率をDPとする。こうするとDPテーブルは\(1\)次元で良い。
解答
#atcod...
AtCoder [AtCoder][競プロ][DP][Educational DP Contest]H-Grid 1
Educational DP Contest
問題
問題キャプチャ。
方針
単純な漸化式で良い。\(H\times W\)のDPを作り、マスが"#"のときは\(dp = 0\)として、マスが"."の...
AtCoder [AtCoder][競プロ][DP][Educational DP Contest]G-Longest Path
Educational DP Contest
問題
問題キャプチャ。
方針
最初にリストに各点から到達しうる点を収納する。DPとしては、\(dp(i)\)を「頂点\(i\)」から開始するパスで最も長...
AtCoder [AtCoder][DP][Educational DP Contest]F-LCS
Educational DP Contest
問題
問題キャプチャ。
方針
Longest Common Subsequence (LCS)の問題。
蟻本に従う。長さを求める問題は多い...
AtCoder [AtCoder][DP][Educational DP Contest][競プロ]E-Knapsack 2
Educational DP Contest
問題
問題キャプチャ。
方針
設定は同じ問題。
上の問題と同じだけど、\(W\)が大きいので、\(NW\)のDPテーブルを作成することはできな...
AtCoder [AtCoder][DP][Educational DP Contest]D-Knapsack 1
Educational DP Contest
問題
問題キャプチャ。
方針
\(N\)が小さく、\(W\)が大きい。また\(v_i\)も大きいので、計算量が\(O(NW)\)となるようにする。蟻本に...
AtCoder [AtCoder][DP][Educational DP Contest]C-Vacation
Educational DP Contest
問題
問題キャプチャ。
方針
配列を\(3\)つ作る。
解答
#atcoder template
def main():
impor...
AtCoder [AtCoder][DP][Educational DP Contest]B-Frog 2
Educational DP Contest
問題
問題キャプチャ。
方針
Frog 1の強化版。計算量は\(O(NK)\)かかる。
解答
#input
n, k = map(int, ...