問題 問題概要 桁dpの問題 類題の私のメモ mmxsrup.hatenablog.com 解法 dp[i][j][k][l][m]という配列を作り埋めていく。 整数pを考えた時に、i番目の桁まで考えて、j=1の時は考えている数がp未満であることが決定していて、j=0の時はp以下である。 k=1の時…

問題 問題概要 桁dpの問題 解法 dp[i][j][k][l]という配列を作りdpで埋めていく感じ。 整数pを考えた時に、i番目の桁まで考えて、j=1の時は考えている数がp未満であることが決定していて、j=0の時はp以下である。 k=1の時はすでにi番目までに数字3を含んでい…

問題 問題概要 数字を並び替えた時に、条件を満たし、もっとも得点を獲得できる時の得点を求める。 解法 数字の数の最大値が14である。数字をすべて並び替える解法だと、計算量が(n!)になるので、TLE。そのためには計算量を(2n)にしなければならない。そこで…

問題 問題概要 チェビシェフ距離の最大のものを探す 解法 表を左上から右下へ、右下から左上へ、右上から左下へ、左下から右上へチェビシェフ距離を動的計画法で埋めていった。例えば、左上から右下へ埋めていく場合を考えると、現在見ているマスの左下、左…

問題 問題概要 サイコロを降って、目の合計がK以上になるサイコロを振る回数の期待値を求める問題。 解法 漸化式を用いて動的計画法で解く。 ミス 漸化式をすこし間違えた。dp[i] := (これまでの目の合計が i のとき、合計が k になるまでに降ることになる回…

問題 問題概要 省略 解法 dp問題。 ミス オーバーフローに注意。dp[何番目の変数か][合計値] := (整数の組みの個数) とおく。変数を一つずつ増やしてみていく。漸化式はdp[i][j] += dp[i - 1]=%20k">j - kとなる。それぞれの変数は0からnまでとるので、kを0…

問題 問題概要 省略 解法 bitDP。どの商品をすでに購入したかを示す集合を要素として持ち、dpをすればいい。集合が決まっている時の、支払う金額の最小値を求めておけば、その集合内でどの順番で商品を買ったかは関係ないので、dpで解ける。 dp[mask] := (ma…

問題 問題概要 省略 解法 簡単に漸化式がたつ、dp。dp[i] := (iマスに行く方法のパターン)とおくと、漸化式は、dp[i] = dp[i - 1] + dp[i - 2]となる。これは、iマス目に行くには、i-1マス目から1で進む、または i-2マス目から2で進むのどちらかであるっこと…

問題 問題概要 省略。 解法 dp[i番目までのおもりを見た時][左側の重さj] := (trueならある)というbool型の配列を用意して、i番目のおもりの時に、左側の重さがjが存在するかをdpで探索していく。単純におもりが左の天秤なのか右の天秤なのかでやってしまう…

問題 問題概要 省略 解法 この問題は町どおしを有向グラフでつないでおり、現在の町の番号は増える方向に必ず増えるように条件が与えられている。そして、残り残金も減る方向に行くので、この問題はDAGグラフで考えることができ、dpで解くことが出来る。 dp[…

問題 問題概要 省略 解法 X進数で表した時17となるXを求める。17の1が数字X分の大きさを持つので、X + 7 = nより X = n - 7を解答として出力すればいい。ただし、17ということは少なくとも８進数以上であることを意味する。X = 8のときn = 15より、nが15より…

問題 問題概要 カップ麺を買う。買っていく途中で所持金が素数になるとはじめの所持金に戻ることができる。ただし、1つの素数につき、1度だけしか戻ることはできない。最大でいくつのカップ麺を買うことができるかを求める。 解法 まず、所持金以下の数字の…

問題 問題概要 共通部分文字列の問題。ただし、連続した文字列でなければならない 解法 単純なdp。文字列s1とs2の両方を何文字目ま見ているかという要素を配列の要素と持つdpを考えればいい。 dp[i][j] = dp[s1のi文字目までで考える][s2のj文字目までで考え…

問題 問題概要 二本の竹がある。二本の竹から任意に注文された竹の長さを切る。多くの注文に答えられるように切るとき、最大いくつの注文に答えられるかを求める問題。 解法 まず注文された竹の長さを昇順にする。竹が短いものから注文に答えていくのは貪欲…

問題 問題概要 都市0から都市Nへ移動する。都市iから都市i+1にj日目に移動するとき，Di*Cj疲労度がたまる。都市0から都市Nまで移動した時の疲労度の最小を求めよ．ただしM日以内にNに到達しなければならない。 解法 都市iにいて，その時j日目の状態において…

問題 問題概要 服を選んで、|Cx1 - Cx2| + |Cx2 - Cx3| + … + |Cxi-1 - Cxi| の最大値を求める問題。 解法 動的計画法で解ける。i日目までの服の選び方を決めたとき，i + 1日目以降について服を選んで目的の値を最大化する際には，1日目からi - 1日目までの…

問題 問題概要 回転ずしで美味しさが最大になるように寿司を取る。ただし２回連続ですしを取ることはできない。 解法 1をすしを取る、0をとらない、とすると、 1010 1001 0101 0010 のようなパターンが続くことになる。それを漸化式で表すと、 dp[i][0] = ma…

問題 問題概要 M個のクエリ満たす数字の並びを求める問題。 解法 まず、 どのような数字が数字の集合としてあり得るのかを計算してflagに入れておく。そして漸化式でdpを解く。感覚的には空集合の場合の数から全集合の場合の数へ、集合の数を増やす感じに計…