問題ページ 解法 木DPをする。dp[v][i][j] = (頂点vを根とする部分木でi回辺を切っていて頂点vの連結成分以外は問題文の条件を満たし、頂点vの連結成分が全てバッテリー(j=0)orそれ以外(j=1)のときの連結成分の頂点の重みの和の最小) とする。不可能な場合は…

問題ページ 解法 きたまさ法メモ - よすぽの日記 この記事を自分なりに理解したメモ 問題では1-indexになっているが0-indexで扱うとする。つまり以下の数列Aの第n項を求めろという問題になる。 A[i] = 1 (i<k) A[i] = A[i-1] + A[i-2] + … + A[i-k] (i>=k) 行列累乗を使えばO(K^3N)で解ける(cf. 蟻本p114</k)>…

問題ページ 解法 dp[i] = (i文字目までを考え、i文字目を'1'にしたときのスコアの最大) としてDPする。dp[i] = (区間[0,i)に内包される区間で得られるスコア, 全部'0'で0以上にはなる) + (i文字目を'1'にしたことで得られるスコア) = max(0, max(dp[j], j

問題ページ 解法 花を削除するのではなく条件を満たしつつ追加していくと考える。高さが低い花から順番に挿入していくと考える。dp[i] = (高さがiの花を挿入したときの美しさの最大)としてDPをする。dp[i] = max(dp[j], j

問題ページ 解法 寿司がa[i]個乗っている皿がどこにあったとしても選ばれる確率に影響はない。したがってN要素の数列a[i]ではなくcnt[i]=(i個乗っている皿の数)と情報を持つことができる。 dfs(x, y, z) = (1個乗っている皿がx枚、2個乗っている皿がy枚、3個…

問題ページ 考えたこと 全パターンについて数え上げなので確率で考える ペア(A[i], A[j])について反転している確率を求めてこれを足して2^Qを掛ければよさそう A[i]>A[j],i

問題ページ 考えたこと まず部分点を取りに行く 木を燃やすときにi番目が燃えているがi-1番目を燃やさずに飛ばすような方法はない 状態がN^2個で収まりそう dp[反時計回りにi個燃やした][時計回りにj個燃やした] = (かかる最大の時間) みたいなDPをしたい 遷…