期待値でも遷移さえわかれば dp で求まるというやつ。 dp と メモ化再帰の両方で解いてみた。 a,b,c = map(int,input().split()) dp = [[[0]*101 for _ in range(101)] for i in range(101)] for i in range(100,a-1,-1): for j in range(100,b-1,-1): for k…

３次元 dp するときに、r,c,k のうち k だけ、計算量が小さいときは、 dp = [[[0]*c for _ in range(r)] for _ in range(k)] と書いた方が実行時間が短くなるという知見を得た。というかこう書かないと TLE するのだがなぜ？ def main(): import sys r,c,k =…

dp の巻き戻しするやつ。dfs をして頂点を探索する際に、stack (deque) に次の頂点を入れる前に、dp を変更する前の要素を入れておくことで、dfs順に頂点を探索するときに、行き止まりについてから、一つ前の頂点に戻る時にその時点での dp を再現することが…

解法１ dp[ i ][ j ][ k ] : i 行 j 列まで見たときに差が k になれるかどうか、なれるなら１、なれないのなら０を記録する。遷移は c = abs(a[ i ][ j ] - b[ i ][ j ]) として (dp[i+1][ j ][k+c] = 1, dp[i+1][ j ][abs(k-c)] = 1 if dp[ i ][ j ][ k ] =…

区間dp の問題。区間dp とは、dp[ i ][ i+j ] = list[ i : i+j ] での最大(最小)値として、最大値の遷移を考えるもの。 今回は、dp[ i ][ j ] = ケーキが i+1 番から i+j+1 番まで残っているときの JOI 君の取り分の最大値 として問題を解く。 ケーキが円状…

タイトルからして dp だと思ったら解説は全探索だった。本質的には dp もメモ化全探索みたいなところあるけど。 w_i の制約が特徴的で max(w_i) - w_1 dp[ i ][ j ][ k ] で i 番目の荷物まで見たときに、j 個の荷物を入れて、 重さが j * w_1 + k となって…

bit dp の問題。ゴールした順に bit を作っていくとうまく dp が作れる。 例えば 1 よりも 2 が早くゴールしているときは、今ゴール済みの人を s で表すと、 s & 1 == 0であれば、まだ１がゴールしていないので s から s | 1 n,m = map(int,input().split())…

bit dp の問題。dp[ i ][ k ] = (a,b) として、今まで通った頂点を表す bit i と今いる頂点 k が入りその時の最小値 a と最小値をとりうる通り方の総数 b が保管されている。 k から次の頂点 j に行けるのは i の j の位が０であるときで、 かつ、dp[ i ][ k…

自力AC。解説とは若干違った。むしろ解説がよく分からん。 ぱっと見で01ナップザック問題じゃんとなり、dpするだけなのかと普通の (N*T) の二次元dp を実装したらサンプル３が合わず考えると、T-1 秒までなら T 秒を超えても注文ができるのが原因だと分かる…

i 文字目を A にした時の文字列の作り方の総数を f(i,0) = dp[i-1][0] として f(n) = sum(dp[n-1]) を求める。 例えば７文字の作り方の総数 f(7) を考えるときは新たに条件を満たさなくなるのは、 ○○○○AGC、○○○○GAC、○○○○ACG、○○○A○GC、○○○AG○C、 となるもの…

25分で d まで順調に解けたが e,f がどうにもできず終了。５完の道は遠い。 解説を読んで dp で実装してみたがなかなか手ごわかった。Unrated なので難易度がはっきりしないが本来なら青diff になっているかも。 dp[ i ][ j ] を （An の大きいものから i 番…

解説AC。文字列の偶数番目と奇数番目で条件をかえながら dp を作った。 文字列の長さが奇数のときは、2つ飛ばしを2回まで、または3つ飛ばしを一回まで使うことができる。 よって dp[i][[j] を i = i 番目の数字、 i が偶数なら j = 0（もう一つ飛ばししかで…