動的計画法(DP)
問題(A) 問題(B) 提出コード(B) Bの問題においてK=2とすればAの問題と同じになります。 解法 個目の足場に行くための最小コスト、とします。すると、 が答えになります。 あとは、 となります。ここで、は1以上以下かつ、が0以上となるような数字です。 今回…
ということで、5日のDPまとめコンテストの予行練習も兼ねてTypical DP Contestを埋めていきました。解いた感想を書いていこうかなと思います。 AtCoder Virtual Contest 目次 目次 A - コンテスト B - ゲーム C - トーナメント D - サイコロ E - 数 F - 準急…
問題 提出コード 解法 bitDPです。だんだん詰め合わせ感が増えてきました。 同じ階層でからに移動するパターン数 とすると、これをの行列に見立てて乗すると、が答えになります。 を求めることさえできれば、あとはこの行列式のを求めていき、程度で答えが求…
問題 提出コード 解法 区間スケジューリングのように、区間の終わりの部分に注目すると、LISに帰着させることができます。 まず、中心座標はx軸上に存在しているので、それぞれの円について、中心座標とがわかっているとき、円と軸が接する2点は、とになりま…
問題 提出コード 解法 bitDPです。 期待値の考え方については、こちらの問題のおかげですんなりいきました。 ARC085 C - HSI - ツバサの備忘録 座標においてある物の状態がである場合に、そこから全ての物を倒すまでに投げるボールの回数の期待値 とします。…
問題 提出コード 解法 基本的な考え方は普段のナップサックと同じで、ある重さになるような荷物の選び方の中での価値の最大値、を求めていきます。 今回、荷物には色が塗られており、種類以下でナップサックに荷物をつめなければなりません。 ということで、…
問題 提出コード 解法 駅で止まるような駅までのパターン数、のようにしていきたいところですが、連続して何駅止まったか、という情報が必要になるので無理です。 逆転の発想をして、駅を通過するような駅～のパターン数、としましょう。 ダミーの駅というも…
問題 提出コード 解法 制約をみてもわかるように桁DPです。 とします。は、上から桁目を決める段階、という意味です。は、今作成している数字の桁和をで割った余りがであるという意味です。は、今作成している数字が未満であることが確定しているかどうか、…
問題 提出コード いきなり難易度高くないですか…？ 解法 左右それぞれの山に積まれている物の合計個数の偶奇によって、どちらのターンかは一意に決まります。 が偶数のとき、左右の合計が奇数であれば、次は後攻、偶数であれば先攻です。 が奇数の場合はこの…
問題 提出コード 解法 はじめに、番の人が番の人に勝つ確率、としておきます。 番目の人が、第ラウンドで勝つ確率、とします。 初期状態はであり、答えはをすべて見ればよいです。 簡単に言えば、番目の人が第ラウンドで戦う可能性のある相手の集合をとした…
問題 提出コード 復習問題だったのですが、見事MLEを吐きました。 解法 を素因数分解したときに登場する2の個数、とします(3,5も同様です)。 基本的な方針としては、 回サイコロを振ったときに、2が回、3が回、5が回登場するような確率 とします。4は2が2回…
問題 提出コード DPまとめコンテストに向けて埋め＋復習をしていこうかと思います。 解法 基本的なDPの1つではないでしょうか。 問目までを解き終えた状態で、得点がになるような方法があるかどうか として、1がある、0がない、とします。初期状態はです。す…
問題 提出コード まずは、レベルバーガーをすべて食べたときの、食べる全体の枚数および食べるパティの枚数を求めます。 食べる全体の枚数をとすると、 となります。 食べるパティの枚数をとすると、 となります。 初期値は、です。 答えは、再帰によって求…
問題 提出コード なんかこの問題の解説すごくむずかしいですね 解法 Nの制約が少ないので、現在のメモリの状態に対していろいろすることを考えます。ということで、bitDPです。 2進数に対し、小さい桁から順番に頂点の番号を割り当てていきます。 例えば、10…
問題 提出コード 高速化がなかなか思いつきませんね… 解法 まずは、制約からbitDPをエスパーで思いつきます。 グループの状態がのとき、これを分割したときに作成できるスコアの最大値 とします。はビットにより表現できます。 を分割して、とに分けたときに…
問題 提出コード 解法 部分点が、どうせ男女の組み合わせについてすべてのパターンを試すんだろうなぁ、という感じがしたので、どうせ男子か女子どちらかのみを探索すると答えを求めるようにすることで高速化をするのかなぁ、という気持ちになります。 とい…
問題 提出コード 解法 番目までのサプリメントを飲む方法数 とします。 番目のサプリメントを飲むときは、 番目のみを1日で飲む 番目と番目の2つを1日で飲む 番目から番目の3つを1日で飲む というように、同時に飲むこともできます。 しかし、番目から番目の…
問題 提出コード 解法 CはDPのC!(n回目)解説PDFによるとオーバーキル解法だそうです… までを利用して、合計得点を10で割った余りがとなるような得点の取り方の最大値 としてDPを解いていきます。 これは、 で解くことができます。 最終的な答えは、 の、の部…
問題 提出コード 解法 ナップサックと書いてあるのでとりあえずDPを考えます。 をすべての重量から引いていくと、どれも0~3のいずれかの重量に置き換えることができます。 この重さを利用して、次のようなDPを考えていきます。 番目までの荷物の中で、個使用…
問題 提出コード サンプル3についてなんとなく考えると、不必要なカードは2,3,4の3つであり、これはすべてのカードの中で小さい3つを選ぶ形になります。 ということで、なんとなく、昇順にソートすると前の方が不必要、後ろの方が必要なカードになりそうなこ…
問題 提出コード 解法 DPをします。 番目までの薬品で、がグラム、がグラムになるような選び方の最小値 とします。 初期値は、、それ以外はです。 あとは、 という遷移をしていけば大丈夫です。 最終的な答えは、 となります(ここで、は1以上です)。
問題 提出コード 方針がたってから遷移をバグなく求めるまでになんと半日かかりました！ 解法 桁DPです。 というのも、2進数になおした2つの数字のペアについて、それぞれの桁についてありうる桁の組み合わせは、 の3種類のみです。 そして、これらの組み合…
問題 提出コード DPをします。 まずは、下準備をします。 ある高さについて、幅がのとき(つまり、本の棒があるとき)に、横線の置き方がいくつあるかを計算します。 これをとします。 のとき、横線はおけないのでです。 のとき、横線を置くか置かないかの2通…
問題 提出コード CはDPのCですね！ 解法 動的計画法を利用します。 数列のi番目までのうち、j個の要素を足した結果がkになるようなものの個数 とします。 すると、 右辺の左の項は、を使用しないパターン(1つ前の個数がそのまま引き継がれます)、右の項は、…
問題 提出コード 解法 真っ暗な部屋が多くて16個しかないので、真っ暗な部屋に関する何かしらの情報をbitで持つことができます。 基本的な考え方は、幅優先探索です。 例えば回指示を出すとしたとき、指示列の選び方は種類になります。全ての部屋に対して、…
問題 提出コード 解法 これ自力で解ききれなかったの悔しいですね… dp[i][j][k] = k回目の移動でiからjに移動するときの、それまでの移動距離の合計の最小値 とします。こうすることで、持っているにんじんの個数は自動的にkになります。 そして、 dis[i][j]…
問題 提出コード ある区間を0にしつつ、うまいこと累積和を計算していきます。 今回は、DPを使って考えました。 i+1 ~ i+Kが0の区間だった場合、i+1~i+Kは無視してよく、i+Kに、iまでの累積和が存在することと同じになります。 ということで、今iについてみ…
問題 提出コード 解法 後ろの方から見ていくと見通しが良くなるのかな、と思いきやそうでもありませんでした。 番目のガソリンスタンドで燃料を補給する場合の、~番目のガソリンスタンドの建て替え方 とします。 仮に今燃料が満タンの状態で番目のガソリンス…
問題 提出コード 解法 動的計画法で答えを求めていくことを考えていきます。 まずは特徴についてです。 この問題では、0がとても重要なものになっています。 数列に0が存在していた場合、0は何回2で割っても0になるので、この部分を利用して与えられたの調整…
問題 提出コード 解法 正四面体数を記録して、重複可能ナップサック問題を解いていきます。 dp[i][j] = i番目までを使用して、数がjになるような組み合わせの中の最小個数 = i番目の正四面体数 とすると、 dp[i][j] = min(dp[i-1][j],dp[i][j-]+1) となりま…
