DP

No.458 異なる素数の和

Quiz https://yukicoder.me/problems/no/458 Submit https://yukicoder.me/submissions/339334 解法 dp[i] : i を異なる素数の和で表した時の最大の和の回数 答えはdp[N] 考察1 dp[i]をより小さいdpで埋めていく よくあるDP しかし今回はダメ dp[7] != dp[2]…

C - Infinite Grid

Quiz https://atcoder.jp/contests/s8pc-6/tasks/s8pc_6_c Submit https://atcoder.jp/contests/s8pc-6/submissions/4981908 解法 editorialの通り 感想 100個くらいつなげて到達可能なら行けそう 迷路で到達可能かどうか、ということで幅優先で解いたらTLE…

No.390 最長の数列

Quiz https://yukicoder.me/problems/no/390 Submit https://yukicoder.me/submissions/19573 解法 公式解説の通りではあるが、各dp[i]についてiの約数を列挙してdpを更新してACした 配るDPがオススメされていたが、制限時間ギリギリそうな列挙でトライした …

No.561 東京と京都

Quiz https://yukicoder.me/problems/no/561 Submit https://yukicoder.me/submissions/336212 解法 動的計画法を使う dp[2][N] dp[i][j] i : 0:東京 1:京都 j : j日目 (0-index)の仕事を終えた後のお金 とする 前日の稼ぎと当日の稼ぎの関係は 前日東京→ 当…

No.65 回数の期待値の練習

Quiz https://yukicoder.me/problems/no/65 Submit https://yukicoder.me/submissions/335985 解法 振る回数の更新式は提供されている E(K)以降は、もうK回を達成しているので振る回数は0であることに気づけば、後ろからのDPができる

No.314 ケンケンパ

Quiz https://yukicoder.me/problems/no/314 Submit https://yukicoder.me/submissions/330500 他の人の解法 dp[i][j] : i番目まで見たとき、ケンの数が j である場合の数 解法 私は、直前2つの状態を見れば遷移が決まることから、 dp[i][j][k] i 番目まで見…

No.4 おもりと天秤

Quiz https://yukicoder.me/problems/no/4 Submit https://yukicoder.me/submissions/330176 解法 天秤の両方を気にするのは大変 重さの合計 / 2 を片側で作れるかで判定すればいい 各重りを使う・使わないで分岐したらO(2100)となってしまう dp[i][j] : i番…

No.786 京都大学の過去問

Quiz https://yukicoder.me/problems/no/786 Submit https://yukicoder.me/submissions/329556 解法 dp[i] : i段登るときのパターン数とする dp[i]は、 dp[i-2]から2段UP dp[i-1]から1段UP という遷移から来ることができるので、 dp[i] = dp[i-2] + dp[i-1] …

E - Union

Quiz https://atcoder.jp/contests/code-thanks-festival-2018-open/tasks/code_thanks_festival_2018_e Submit https://atcoder.jp/contests/code-thanks-festival-2018-open/submissions/4722141 解法 dp[i][j] 整数 i まで見て、iがj個余る場合の数 例 dp…

D - We Love ABC abc104_d

DP

Quiz https://atcoder.jp/contests/abc104/tasks/abc104_d Submit https://atcoder.jp/contests/abc104/submissions/4308261 Note この解説が素晴らしい https://betrue12.hateblo.jp/entry/2018/08/05/230358

D - Mixing Experiment abc054_d

DP

Quiz https://atcoder.jp/contests/abc054/tasks/abc054_d Submit https://atcoder.jp/contests/abc054/submissions/4261224 Note 3次元DPとはいえ恐れるなかれ テストケース テストケース1, 2は間違ったコードでも通りやすい そこでテストケース1に追記した…