https://atcoder.jp/contests/dp/tasks/dp_w 前提知識 データ構造によるDP更新最適化 区間add, 区間max遅延評価セグメントツリー 解説 https://atcoder.jp/contests/dp/submissions/3963076dp[r] := r文字目まで確定していてr文字目が1であり、それ以降は0で…

https://atcoder.jp/contests/dp/tasks/dp_v 前提知識 全方位木DP 解説 https://atcoder.jp/contests/dp/submissions/3955506全方位木DPをする。 dfs1で0を根として普通に木DPをする。 次に、dfs1で作ったDPを改変しながら、dfs2で全ての頂点を根として答え…

https://atcoder.jp/contests/dp/tasks/dp_u 前提知識 O(3^N)でのbitDP 解説 https://atcoder.jp/contests/dp/submissions/3949705制約からbitDP感がある。 dp[msk] := グループが決まったうさぎがmskである場合の点数の最大値 dp[msk]を確定させたいときに…

https://atcoder.jp/contests/dp/tasks/dp_t 前提知識 BITによる更新最適化 解説 https://atcoder.jp/contests/dp/submissions/3980491正直自分で以下のDPを思いついてないので、思いつく過程は分からない。 色々な要素が絡む難しい問題なので、TLEするDPを…

https://atcoder.jp/contests/dp/tasks/dp_s 前提知識 桁DP 解説 https://atcoder.jp/contests/dp/submissions/3949534桁DPをする。 dp[dgt][d][isless] := 上からdgt桁目まで確定していて、各桁の数字の総和modDがdで、K未満かどうかがisless（isless=1なら…

https://atcoder.jp/contests/dp/tasks/dp_r 前提知識 行列累乗によるDP高速化 解説 https://atcoder.jp/contests/dp/submissions/3955540長さKがとても大きい＋Nが小さいという所から、行列累乗感がかなりある。 dp[k][cu] := 長さkの有向パスで最後の頂点…

https://atcoder.jp/contests/dp/tasks/dp_q 前提知識 LIS（最長部分増加列）の派生 インラインDP 解説 https://atcoder.jp/contests/dp/submissions/3973860LISの派生系みたいな問題。 セグメントツリーでLISを解く方法を参考にして解く。 その方法を詳しく…

https://atcoder.jp/contests/dp/tasks/dp_p 前提知識 木DP 解説 https://atcoder.jp/contests/dp/submissions/3949251木DPをする。 木上での数え上げといえば木DPを最初に疑って問題ないと思う。 隣り合う頂点どおしを黒で塗れないということは、部分木の根…

https://atcoder.jp/contests/dp/tasks/dp_o 前提知識 bitDP 解説 https://atcoder.jp/contests/dp/submissions/3973687bitDPで解くのだろうという推測は制約からできる。 無計画に数えると、同じパターンを数え上げてしまうので、男性の方は1,2,,...と固定…

https://atcoder.jp/contests/dp/tasks/dp_n 前提知識 区間DP 解説 https://atcoder.jp/contests/dp/submissions/3955596区間DPをする。 dp(L, R) := [L,R]の区間のスライムを1つにするためのコストの総和の最小値 自分は区間DPはメモ化再帰で実装するのが好…

https://atcoder.jp/contests/dp/tasks/dp_m 前提知識 データ構造による動的計画法更新高速化 解説 https://atcoder.jp/contests/dp/submissions/3948814dp[i][k] := i人目の子供まで配り終えて、残りがk個である組み合わせ dp[i][k]からの遷移を考えると、i…

https://atcoder.jp/contests/dp/tasks/dp_l 前提知識 ミニマックス法 区間DP 解説 https://atcoder.jp/contests/dp/submissions/3948451問題設定がミニマックス法に適しているので適用する。 DPコンテストなのだが、区間DPなので、メモ化再帰で書いている。…

https://atcoder.jp/contests/dp/tasks/dp_k 前提知識 後退解析 解説 https://atcoder.jp/contests/dp/submissions/3948285ゲーム問題のテクとして後退解析がある。 この後退解析をDPっぽくやる手法がある。 dp[k] := k個の石からなる山で先手が勝ち状態か(=…

https://atcoder.jp/contests/dp/tasks/dp_j 前提知識 期待値DP 解説 https://atcoder.jp/contests/dp/submissions/3963610もし考え方違ってたら指摘ください…期待値DPをする。 何番目の寿司かということは特に関係なく、残っている個数毎に集計して問題ない…

https://atcoder.jp/contests/dp/tasks/dp_i 前提知識 確率DP 解説 https://atcoder.jp/contests/dp/submissions/3947967確率DPをする。 dp[i][omote] := i枚のコインを投げて表の枚数がomoteとなる確率 uraを保持しなくてもいいのか？という問題があるが、u…

https://atcoder.jp/contests/dp/tasks/dp_h 前提知識 組み合わせ系の動的計画法 解説 https://atcoder.jp/contests/dp/submissions/3947874mod10^9+7の数え上げはDPの可能性が高いし、マス移動でDPを使う問題は死ぬほどみたせいか、DPの定義が自然と出てく…

https://atcoder.jp/contests/dp/tasks/dp_g 前提知識 トポロジカルソート 解説 https://atcoder.jp/contests/dp/submissions/3947799トポロジカルソートを知っていれば一瞬だが、知らないと解けない。 DPというのは「ある状態を処理するときは、その状態に…

https://atcoder.jp/contests/dp/tasks/dp_f 前提知識 動的計画法テク「遷移が多い場合は貪欲法を使うことで最適であろう遷移を絞ることができる」 解説 https://atcoder.jp/contests/dp/submissions/3947645恐らく想定解ではないライブラリによる筋肉解法で…

https://atcoder.jp/contests/dp/tasks/dp_e 前提知識 動的計画法 解説 https://atcoder.jp/contests/dp/submissions/3946715ナップサック問題のよくある変形。 状態として保持する物を変形して解く。 というより、解く流れとしては、1. dp[N][W]では状態数…

https://atcoder.jp/contests/dp/tasks/dp_d 前提知識 動的計画法 解説 https://atcoder.jp/contests/dp/submissions/3946683一般的なナップサック問題。 dp[i][tot] := i番目までの商品を入れて、重さの総和がtotである場合の価値の総和の最大値 ナップサッ…

https://atcoder.jp/contests/dp/tasks/dp_c 前提知識 最大最小系の動的計画法 解説 https://atcoder.jp/contests/dp/submissions/3946364DPだという前提で考えると、 dp[i] := i日目の活動を終えたときの幸福度の総和の最大値 というDPが思いつく。 しかし…

https://atcoder.jp/contests/dp/tasks/dp_b 前提知識 最大最小系の動的計画法 解説 https://atcoder.jp/contests/dp/submissions/3946249EDPCのAの強化版であり、同じDPで同じ方針で解く。 dp[i] := i番目の足場にたどり着くためのコストの総和の最小値 最…

https://atcoder.jp/contests/dp/tasks/dp_a 前提知識 最大最小系の動的計画法 解説 https://atcoder.jp/contests/dp/submissions/3946204最小値のDPを書く。 dp[i] := i番目の足場にたどり着くためのコストの総和の最小値 最小値のDPを書く場合はすべての要…

本記事は書きかけであり、初心者が書いている記事なので、初学者はあまり参考にしないように セマンティックセグメンテーション ディープラーニングにおけるセマンティックセグメンテーションのガイド2017年版 Resources of semantic segmantation based on …

https://yukicoder.me/problems/no/762 前提知識 動的計画法（木DPの方が近いかも） 解法 https://yukicoder.me/submissions/307975DPで解く。 dp[cu][t] := 頂点cuで終わり、PDCAのt番目まで正しく来ている組み合わせ rep(cu, 0, N) if (S[cu] == T[0]) dp[…

https://yukicoder.me/problems/no/763 前提知識 木DP 解説 https://yukicoder.me/submissions/307974木DPをする。 dp[cu][erase] := cu以下の部分木において、頂点cuを消した(erase=1なら消した)ときの木の個数 最初はdp[cu][0] = 1（頂点cu自身）、dp[cu][…

https://yukicoder.me/problems/no/765 前提知識 ローリングハッシュ 考察過程 1. どこから手を付けていいか分からないので、とりあえず全探索対象を探す 2. 削除文字を全探索すると、難しそうなので、だめそう 3. 回分なので、中心も全探索できそう 4. する…

https://yukicoder.me/problems/no/768 前提知識 バックトラック 全方位木DP 考察過程 1. 全頂点についてなにかするやつは全方位木DPを真っ先に疑ってしまう 2. 違う場合の方が多いのだが、今回はそれで行けそう 3. 一般化すると、全頂点の判定はまず1頂点に…

https://yukicoder.me/problems/no/769 解説 https://yukicoder.me/submissions/307913色々な変数を定義して、シミュレーションをしよう。 cards[i] := プレイヤーiが何個のカードを出したか cu := 現在のプレイヤー dir := 現在の方向（1か-1） draw2 := ド…

https://yukicoder.me/problems/no/771 前提知識 bitDP 解法 https://yukicoder.me/submissions/307901制約からbitDP感がある。 その方向で考えると、以下のDPができる。 dp[msk][lst] := 今までmskの本が本棚に入っていて、最後の本がlstのときの醜さ ここ…