これまたすごく典型的な DP！！！ 「状態遷移」を意識して取り扱う DP。ごく一部の界隈では耳 DP と呼ばれていたりもするかもしれない。 問題へのリンク editorial この問題の前提知識 ナップサック問題を解く DP が自力で書けること 1000000007 で割ったあ…

EDPC C - Vacation と良く似た問題だと思う！！ あと、幅が狭いグリッドでは DP が疑われることが結構多い！ 問題へのリンク 問題概要 長さが の数列が 2 つ ( と ) 与えられます。 各 に対して、 と のいずれかを選ぶことで、新たに数列 を作ります。 こう…

左右からナップサックした結果を前処理する系！ (他の解法もあり) 問題へのリンク editorial 問題概要 (意訳) (実際の問題文は時刻に関する問題) 個の品物がある。それぞれ の番号がついている。番号が の品物は 価値が 重さが となっている。これらを 2 つ…

5 + 7 + 5 = 17 なの、よくできてる！ 問題へのリンク 問題概要 正の整数 が与えられる。 以上 以下の数値からなる長さ の数列 であって、以下の条件を満たすものの個数を 1000000007 で割ったあまりを求めよ。 整数 が存在して、 の区間 の総和が の区間 の…

こういうのを素早く解けるようになりたい 問題へのリンク editorial 問題概要 頂点 辺の重み付き無向グラフがある。各頂点 には そこで売ってるパンを買ったときの美味しさ そこで売ってるジャムの種類 そこで売ってるジャムを買ったときの美味しさ という 3…

これ系、この問題以降はたくさん見るようになったけど、この問題が先駆けとなった気がする 問題へのリンク 問題概要 'a', 'b', 'c' のみからなる長さ の文字列 が与えられる。 に以下の操作を好きな順序で好きな回数だけ行って得られる文字列が何通りあるか…

ごちゃごちゃとばぐらせながら何とか通した... 問題へのリンク 問題概要 要素の数列 が与えられる。この数列の 通りの区間それぞれについての 区間内の要素の部分集合であって総和が であるものの個数 の総和を求め、998244353 で割ったあまりを求めよ。 制…

部分文字列の遷移は愚直に求めた。。。 問題へのリンク 問題概要 長さ の文字列 c と、短い文字列 s, t が与えられ、'a'〜'z' と '?' からなっている。'?' を埋める方法のうち、 c の連続する部分文字列として s を含む箇所の個数から c の連続する部分文字…

こういうの素早く書けるようになるにはどうしたらいいんだろう... 問題へのリンク 問題概要 'A', 'G', 'C', 'T' のみからなる長さ の文字列のうち、「どの隣接した 2 文字を swap しても "AGC" を連続部分列として含まないもの」が何通りあるか求めよ。 制約…

郡山駅のベンチで寒さに震えながらやる問題ではなかった...必要以上に複雑にしてしまった。。。 問題へのリンク 問題概要 すぬけさんが、座標 0 と との間を行ったり来たりする。行って方向転換できる場所は整数座標のみである。 このとき、各区間 [ ] () に…

これ好きなん！！！ 400 点問題が問題分読んで 5 秒以内に方針立ったのは珍しいので、成長かもなん。 そして、DEGwer さんや chokudai さんが「DP は割とコーディングしながら細部詰めてる」と言っていたので、それを実践してみて、確かに良さそうかもなん。…

RUPC 2018 の思い出。桁 DP なん。 問題へのリンク 問題概要 ごちうさ数とは、10 進法表記において「5?13」を含む正の整数のことである。? は 0〜9 のいずれでもよい。 以下の正の整数のうち、ごちうさ数が何個あるかを求めよ。 制約 解法 桁 DP。 一目、51?…