DP

D - Multiple of 2019

Quiz https://atcoder.jp/contests/abc164/tasks/abc164_d 解法 (editorial) 右からi番目までを数字として見て mod 2019した結果を持っておく 入力の数字は文字列で受け取り、1桁ずつ処理すれば桁あふれしない modの結果が同じ数字のところは、それを組み合…

JOI 古本屋(Books)

DP

Quiz http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0561 AC code http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4146908#1 要素 ソート 累積和 DP 解法 各ジャンルごとに高い順にソートしてよい そしてDP // ジャンル i までで // 合…

Combination of Number Sequences

プログラミングコンテスト攻略のためのアルゴリズムとデータ構造作者: 渡部有隆,Ozy(協力),秋葉拓哉(協力)出版社/メーカー: マイナビ発売日: 2015/01/30メディア: 単行本(ソフトカバー)この商品を含むブログ (7件) を見る Quiz http://judge.u-aizu.ac.jp/…

D - Digits Parade ~右からDP, 左からDP~

Quiz https://atcoder.jp/contests/abc135/tasks/abc135_d 内容 解法というか、左からDP, 右からDPのどちらでも解けますというメモです 解法 文字列の左からDP AC Code https://atcoder.jp/contests/abc135/submissions/6595777 公式解説と同じで、DPの添字…

Bit DPと再帰関数

Quiz No.771 しおり https://yukicoder.me/problems/no/771 AC https://yukicoder.me/submissions/353958 他の人の解説記事 はまやんはまやんさん https://www.hamayanhamayan.com/entry/2019/01/02/214632 解法 Bit DP 蟻本(v2)で言うと、p173の巡回セール…

D - 徒競走 abc041_d

Quiz https://atcoder.jp/contests/abc041/tasks/abc041_d Submit https://atcoder.jp/contests/abc041/submissions/5137686 解法 公式解説の通り メモ化再帰を使用 感想 この問題は昔も解説ACしたもの。解説pdfを見て「難しい、よく解けたな」と思う 「メモ…

No.496 ワープクリスタル (給料日前編)

Quiz https://yukicoder.me/problems/no/496 Submit https://yukicoder.me/submissions/342341 類似問題(一次元) https://tdpc.contest.atcoder.jp/tasks/tdpc_contest https://tdpc.contest.atcoder.jp/submissions/5127160 解法 上記一次元のDPと同じ解…

配るDP 〜Strange Bank〜

DP

Quiz https://atcoder.jp/contests/abc099/tasks/abc099_c Submit https://atcoder.jp/contests/abc099/submissions/5118558 感想 けんちょんさんの記事 https://qiita.com/drken/items/ace3142967c4f01d42e9 を読んでいたらStrange Bankを「配る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に追記した…