https://yukicoder.me/problems/no/783 前提知識 動的計画法 解説 https://yukicoder.me/submissions/309701dpで解く。 dp[len][prepre][pre][c] := 長さlenの門松列列であり2つ前の竹がprepreで1つ前の竹がpreであり、お金の残高がc円であるときの長さの総…

https://yukicoder.me/problems/no/781 解説 https://yukicoder.me/submissions/310016原点Oを中心とする、半径root(R)の円の式は x^2+y^2=Rとなる。 よって、格子点は x,yが整数でx^2+y^2=Rを満たす頂点である。 Rの最大値が10^7であるが、このときのx,yの…

https://yukicoder.me/problems/no/780 解説 https://yukicoder.me/submissions/309502場合分けして解く。 男の子はヤスオくん含めてA+1人いる。 よって、女子はその人数以上じゃないとヤスオくんは遊べない。 なので、A+1≦BならYES、そうでないならNO ペア…

https://yukicoder.me/problems/no/779 解説 https://yukicoder.me/submissions/309481日付を前後関係を維持しながら数値に変換するエンコーダを書く。 f(y, m, d) := y年m月d日を数値に変換する あとは、それを使って大小比較する。 int Y, M, D; //-------…

Educational DP Contest Educational DP Contest 典型的なDPの問題をまとめたコンテスト 自分の記事へのリンクまとめとして書く ネットを漁ると色々な人が問題・前提知識について解説を書いているので、問題に詰まった場合は適宜ぐぐるといい あと、前提知識…

https://atcoder.jp/contests/dp/tasks/dp_z 前提知識 CHTによるDP高速化 解説 https://atcoder.jp/contests/dp/submissions/3956069以下の解説の前にCHTについてわかっていないと以下は理解できない。 とりあえず、複数の1次関数にxを代入したときの最小値…

https://atcoder.jp/contests/dp/tasks/dp_y 前提知識 包除原理 解説 https://atcoder.jp/contests/dp/submissions/3956127同様の包除原理問題を見たことがあったから、包除原理で解くと分かったので、考察過程は無いです。 わかりやすさのために段階的に解…

https://atcoder.jp/contests/dp/tasks/dp_x 前提知識 動的計画法テク「選択するものを最初にソートしておくと、DPできたり、状態を同一化できたりする」 解説 https://atcoder.jp/contests/dp/submissions/3980762動的計画法で困るのが、順番が任意である場…

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の有向パスで最後の頂点…