srupのメモ帳

競プロで解いた問題や勉強したことを記録していくメモ帳

dp

aoj 1176 Planning Rolling Blackouts

問題 問題概要 長方形が与えられ, そのますに値が入っている. 長方形を分割してくが, 分割方法は区切られた長方形を一つ選び, それを縦か横どちらに切って分ける. 分割できるのは, 分割後に任意のグループを一つ選び, 抑制需要(残ったグループのますの値の合…

yukicoder No.484 収穫

問題 問題概要 i番目の木はA[i]の実が実る. 時刻1で隣の木にいどうすることができる. 移動しなくてもよい. このような条件ですべての実を回収するのにかかる時間の最小値を求める. 解法 区間dpで解けるみたい. 今回の問題を考えるにあたって重要な考察は, i…

ABC 054 D - Mixing Experiment

問題 問題概要 タイプAとBの混合比がMa:Mbとなる薬を作らないければならない. 薬局の情報がNこあたえられ, それぞれの薬局でタイプAとBの薬をそれぞれいくら持っているかの情報とその値段が与えられる. いくつかの薬局で薬を買ってそれらをすべて使い, Ma:Mb…

ABC 037 D - 経路

問題 問題概要 任意のマスからスタートして、数字の大きい方へ進める。経路の総数を求める。 解法 dp[i][j]:= y=i,x=jから始めた時の経路の総数 として、再帰関数を用いて、周りの4方向どこへも進めないマスから順に埋めていけばいい。メモ化しておけばTLEに…

yukicoder No.458 異なる素数の和

問題 問題概要 N以下の数字を相異なる素数のみで表すことを考える。素数の数の種類の合計値が最大のときの最大値を求めよ。 解法 dpで解ける。 dp[i] := 合計がiとなるときの和の回数の最大値 として、これをループで求めていけばいい。 ただし、今回注意し…

yukicoder No.472 平均順位

問題 問題概要 毎回のコンテストで解いた問題数における順位があたえられる。すべてのコンテストでの解いた問題数の合計があたえられる。すべてのコンテストでの順位を最小にするときの最小値を求めよ。 解法 dp[i][j] := i番目までのコンテストで、j問解い…

yukicoder No.23 技の選択

問題 問題概要 省略。 解法 期待値dpの問題。 残りのHPを基準に考える(下のソース)。 aを選びとき、(残りHPがiのときの期待値) = (残りHPがi + aのときの期待値) + 1(回) bを選ぶとき、(残りHPがiのときの期待値) = (残りHPがi + bのときの期待値) + 1.5(回)…

ARC 036 C - 偶然ジェネレータ

問題 問題概要 省略 解法 ランダムウォークの表のようなものを考えて、+y方向に、(1-0の数)、-y方向に(0-1の数)として表を考える。そして、dp配列に、dp[i][j][k] := i番目まで見て、(1-0)の最大値がjで、(0-1)の最小値がkの時の場合の数 として、更新してい…

SRM 688 div2 easy ParenthesesDiv2Medium

問題 問題概要 カッコの文字列が与えられる。カッコが対応する形に変更する。ただし変更できる文字の数は、((文字数)/2)+1まで。 解法 動的計画法で解いた。変更できる文字の数に制限があるので、最小の数で対応づけができるものを求めた。dp[i][j] := i番目…

yukicoder No.258 回転寿司(2)

問題 問題概要 N個の寿司が並んでいる。順番に食べていくが、連続して食べることはできない。寿司にはおいしさがそれぞれ決まっている。食べた寿司のおいしさの合計の最大値を求めよ。またどの寿司を食べたかも求める。経路復元。 解法 動的計画法で解く。dp…

yukicoder No.225 文字列変更(medium)

問題 問題概要 SをTにするときの編集距離の最小を求める問題。編集距離のdpの漸化式については以下のサイトが参考になる。 解法 dpで解くことができる。 dp[i][j] := 文字列Sのi番目までで、文字列Tのj番目までを作ることを考えた時の操作回数の最小値として…

codeforces 374 div2 C. Journey

問題 問題概要 有向グラフが与えられる。1からnまで距離T以下で行く中で、辿る頂点の数を最大にする経路を求める。 解法 dpの解法は、dp[i][j] := i個の名所を回って、j番目の名所にいるときの、移動時間の最小値 として更新していけば解くことができた。今…

yukicoder No.412 花火大会

問題 問題概要 組み合わせの数え上げ 解法 まず、すべてソートしてく。全探索をして、それぞれの家族がどのマットを使うかを決める。それが条件を満たしたものであれば、ほかのものは選ぶ選ばないの選択がある。 dpのほうがわかりやすいな。状態数は2つで、1…

yukicoder No.58 イカサマなサイコロ

問題 問題概要 省略 解法 dpで解いた。 dp1[i][j] := 太郎君がサイコロをi回振って、合計がjの時の確率 dp2[i][j] := 次郎君がサイコロをi回振って、合計がjの時の確率 とおいて、漸化式でi=1からi=nまでループを回して埋めていった。 漸化式は単純で、いか…

ABC 026 C - 高橋君の給料

問題 問題概要 省略 解法 上司から直属の部下に対して辺を張り、有向グラフを作成する。それを利用して、dfsを行う。部下がいないとき、つまり、グラフ上で葉の部分に該当する部下の給料は1なので、1を返す。部下が存在するとき、つまり、葉以外の頂点では、…

ABC 021 C - 正直者の高橋くん

問題 問題概要 省略 解法 bfsで解いた。よくある最短距離を求めるときにやる、bfsは一度、到達したところは2回目以降むしをするが、今回は、初めて到達したあとも、その位置に最短距離として、ほかの経路から到達して来る可能性があるので、bfsで初めに到達…

ABC 015 D - 高橋くんの苦悩

問題 問題概要 省略 解法 ナップザック問題に選んでいい品物の個数を制限する制約を追加した問題。 dp[i][j][l] := i番目のスクショまで見て、j枚貼り、幅lを使っているときの重要度の最大値 として、ループで値を埋めていく。 ミス なし。 コード #include <iostream></iostream>…

SRM 698 div2 medium RepeatStringEasy

問題 問題概要 与えられた文字列から、部分文字列として、共通のもの(T)を取り出し、S = T + TのSの長さを求める問題。 解法 まず、与えられた文字列を2つに分ける。その後、その2つの文字列の最長共通部分列(LCS)の長さを求めて、2倍したものが答えの候補と…

yukicoder No.140 みんなで旅行

問題 問題概要 省略。 解法 解説スライド見るとわかりやすい。 kmjp.hatenablog.jp スターリング数は、S(n, k) 区別できるn個のものを区別できないkグループに分類する方法の場合の数を漸化式と表すことができる。 S(n, k) = s(n - 1, k - 1) + k * S(n - 1,…

ARC 011 C - 123引き算

問題 問題概要 省略 解法 dpで解いた。dp[i][j] := i回数字を引いて、jになるなら、true、とおいてループで回して埋めていった。 dp[i][j+k]=trueならdp[i][j]=trueとなるので(ただし、jはngでない)、このことから漸化式らしきものが立てられる。 ミス nがい…

yukicoder No.37 遊園地のアトラクション

問題 問題概要 省略 解法 dpで解いた。dp[i][j] := i番目のアトラクションまで見て、待ち時間の総和がjの時の満足度の最大値、をループで回して埋めていった。やり方は、個数制限なしナップザック問題を解くイメージ。実装方法はcntでi番目のアトラクション…

yukicoder No.27 板の準備

問題 問題概要 個数制限なしナップザック問題。 解法 dp[x] := ita[0]~ita[2]を使い、長さxの板を作るのに、必要な最小の板の枚数と置き、ループで回して埋めていった。 したのは、同じものを選ぶ時に、ループを回して、取れる数まで同じものを取るようにし…

yukicoder No.398 ハーフパイプ(2)

問題 問題概要 省略 解法 dpでできるみたい。 dp[i][j][k][l] := i番目まの審査員まで考えて(0origin)、最小値がj、最大値がkで合計がlの時の場合の数。としてループを回せばいい。言われればそうだなという感じ。 最大最小と合計があれば、状態を区別するこ…

yukicoder No.324 落ちてた閉路グラフ

問題 問題概要 省略 解法 dpで解いた。直線になっていれば即座にdpだろうなと思ったけど、円になっていたからすぐにわからず苦戦した。円になっている時に注意しなければならないことは、0オリジンで考えた場合、頂点0を選んだ場合、もし頂点n-1も選んだら、…

yukicoder No.314 ケンケンパ

問題 問題概要 けんけんパーが何通り考えられか。 解法 dpで解いた。dp[i][j] := i番目まで考えて、j回連続ケンをした時の場合の数を入れて、ループで回した。漸化式は、何回ケンを連続で行っているかによって、場合分けした。 ミス すんなり行けた。 コード…

ARC 060 C - 高橋君とカード / Tak and Cards

問題 問題概要 省略 解法 dpでとく。dp[i][j][k] := x[i]まで見て、選んだ数がj個で、合計値がkの時の場合の数 として、漸化式を立てて、ループを回して計算し、dp[n - 1][j][j * a]の和を取れば回答となる。 ミス 特になし。 コード #include <iostream> #include <cstdio> us</cstdio></iostream>…

天下一プログラマーコンテスト2016予選B B - 天下一魔力発電

問題 問題概要 省略 解法 単純に全ての状態を全探索すると、2nで無理。 dpで解きました。状態を決めるために、何文字目までで'('が何文字あり、最後に反転させた位置が同じであれば、同じ状態とみなせると考えた。 dp[i][j][k] := s[i]文字目まで見て、'('が…

aoj 0550 - Dividing Snacks

問題 問題概要 お菓子に1ミリずつ切り目があり、切れ目ごとに切るためのコストが異なる。コストを最小にして、お菓子を半分ずつに分ける方法は。 解法 dpでとく。 dp[i][j][k] := (お菓子の長さがiでAさんの文がjの時で次ににkさんがお菓子をもらう時の切断…

aoj 0530 - Pyon-Pyon River Crossing

問題 問題概要 省略。 解法 動的計画法でやった。 dp[y座標][x座標][1つ飛ばしジャンプの回数] := (y, xに行くまでの最小の危険度)というdpを考えた。y座標が常に大きくなるので、DAGと考えるので、このようなやり方でやった。また、うまいやり方が思いつか…

aoj 0515 - School Road

問題 問題概要 高校数学で出てくる場合の数の問題。 解法 dpで解きました。(x,y)=(0,0)への行き方を1通りとして、(1,0)は(0,0)からの1通り、(0,1)は(0,0)からの1通りの方法で行くことができ、(1,1)は(0,1)と(1,0)から行く方法があり、(0,1)と(1,0)へ行く方…

yukicoder No.260 世界のなんとか3

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

yukicoder No.220 世界のなんとか2

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

yukicoder No.357 品物の並び替え (Middle)

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

yukicoder No.402 最も海から遠い場所

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

yukicoder No.65 回数の期待値の練習

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

yukicoder No.287 場合の数

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

yukicoder No.286 Modulo Discount Store

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

yukicoder No.44 DPなすごろく

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

yukicoder No.4 おもりと天秤

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

yukicoder No.1 道のショートカット

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

yukicoder No.395 永遠の17歳

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

yukicoder No.385 カップ麺生活

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

aoj 0528 - Common Sub-String

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

yukicoder No.393 2本の竹

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

aoj 0611 - Silk Road

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

aoj 0579 - Hot days

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

yukicoder No.45 回転寿司

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

ABC041 D - 徒競走

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