DP状態:個数
式がいかめしくて戸惑うけど、DP 自体は比較的単純 問題へのリンク 問題概要 個の値 が与えられる。 これらの中から順序を保っていくつか選ぶ。選び方のスコアは、 個の整数 を選んだとしたとき、 で与えられる。このスコアの最大値を求めよ。 制約 考えたこ…
実は DP の添字の取りうる範囲が log オーダーであることを見抜く問題。より高度な問題でもしばしば見られる考え方。 問題へのリンク 問題概要 二次元平面上に点 がある。点 の座標は である。 今、点 1 にいて、原則として点 を順に通過して最終的に点 に到…
個の区間を、プチ区間たちを用いて、最小コストですべて被覆しようという問題。DP 状態の持ち方を工夫することで計算量を小さくしたい。 問題へのリンク 問題概要 個の区間があって、長さが である。これらすべてを 2 種類の区間で被覆したい。 長さが であ…
最初、各マスをタスクに見立てて、タスクの依存関係を考える DAG 上で DP できないかなどと考えたけど、うまくいかなかった。普通にグリッドを左から舐めていく DP でよかった！ 問題へのリンク 問題概要 のグリッドがある。各マスはすでに白色 (文字 '.') …
少し前処理が面倒な DP。PCK の予選突破ライン上の問題のようですね！ 問題へのリンク 問題概要 個の整数 が黒板に書かれている (各整数は 100 桁までありうる)。 奇数の精と、偶数の精がいる。 奇数の精は、黒板に書かれている数字がすべて奇数となるように…
久しぶりに bit ベクター高速化を使った。デバッグがしんどかった。 問題へのリンク 問題概要 長さ の数列 と、長さ の数列 が与えられる。今、次の操作をちょうど 回実行する と を選ぶ と とを swap する 操作実行後の の値の最大値を求めよ。 制約 考えた…
部分和問題の応用問題！ 問題へのリンク 問題概要 個の非負整数 が与えられれる。 これらの整数から 個選んで、総和が の倍数となるようにする。その値として考えられる最大値を答えよ。 の倍数にするのが不可能な場合は -1 を答えよ。 制約 前提知識 この問…
この問題、実は、北大合宿 HUPC の有志コン枠で原案として挙げていた問題とまったく同じだった！！！！！！ 問題へのリンク 問題概要 の順列 の奇妙さを と定義する。奇妙さが であるような順列の個数を 1000000007 で割ったあまりを求めよ。 制約 考えたこ…
JOI 難易度 6 の中では難しい方だと思った！ 問題へのリンク editorial 問題概要 のグリッドの左下マス から右上マス へと至る最短経路 (上または右にのみ移動可能) のうち、以下の条件を満たすものの個数を 100000 で割ったあまりを求めよ。 曲がってから、…
とてもよくある区間分割していくタイプの DP 問題へのリンク 問題概要 個の正の整数 がこの順に一列に並んでいる。これらの整数を 個以下の区間に分割したい。 このとき、「各区間の値の平均値の総和」として考えられる最小値を求めよ。 制約 考えたこと 「…
いかにも ABC-E にありあそうな DP！！ ジャッジへのリンク 問題文へのリンク これとか似てる atcoder.jp 問題概要 個の店がある。 日間にわたって、いずれか 1 つの店で買い物をする。 日目に 番目の店で買い物をしたときの値段は で与えられる (10 の倍数)…
戻す DP シリーズのトレーニング 問題へのリンク 問題概要 (入力形式は多少改変) 正の整数 と、 個の正の整数 が与えられる。これらをランダムシャッフルする。 を満たす最小の を考える。この値の期待値を求めよ (要求精度は )。 制約 考えたこと 各要素 に…
最初、同じ行の「連続する 3 個」しか選べないのだと誤読してしまった... 問題へのリンク 問題概要 二次元座標平面上で、(1, 1) から (R, C) へと格子点を辿って最短経路で進みたい (上か右にしか行けない)。 K 個の座標 () に価値 のアイテムがある。通った…
これ系、この問題以降はたくさん見るようになったけど、この問題が先駆けとなった気がする 問題へのリンク 問題概要 'a', 'b', 'c' のみからなる長さ の文字列 が与えられる。 に以下の操作を好きな順序で好きな回数だけ行って得られる文字列が何通りあるか…
「平均値が A」という制約は上手に扱うテクニックがある。 今回はそれを思いつかなくても解けるけど、思いつくと計算量が落ちる。 問題へのリンク 問題概要 個の整数 からいくつか選ぶ方法のうち、その平均値がちょうど となるものが何通りあるかを求めよ。 …
素朴な DP でもできるけど、実はカタラン数！ 問題へのリンク editorials 問題概要 正の整数 が与えられる。以下の条件を満たす数列 (数列のサイズ は 以上の範囲で自由に選んでよい) の個数を求めよ。 各 に対して、 である である たとえば、 のとき、 の …
