atcoder.jp ゲーム系の問題でDPをするときはメモ化再帰の方が書きやすい気がする。 解法 $ S_i $か0かの選択をする際に、その選択をした結果7の倍数を作れるor作れないことが分かれば、常に最適な行動を取れる。 ということで、前の桁から$ S_i $か0かの選択…

atcoder.jp 解法 T - 0.5分後というのは、T-1分後と言い換えることができる。 T-1秒をこえて、料理を食べることができない場合、ただのナップザックDPで解くことができる。 具体的にDPの定義は次のようになる。 dp[i][j] ← i番目の料理まで食べるかどうか決…

atcoder.jp 解法 3つの条件を上から順に条件1、条件2、条件3と呼ぶことにする。 3つ目の条件が存在しない場合、次のDPで解くことができる。 dp[i][j][k] ← 長さiでi-1文字目がj、i文字目がkであるような条件1,2を満たす文字列はいくつあるか 遷移をする際に…

atcoder.jp 解法 全探索しようとするとO(2N)になってしまうような問題はDPで解けることが多い。 なので、DPで解くことを考えてみる。 i回目の操作F, Gは次のように言い換えられる。 左端と左からi + 1番目の値を計算して、現在の左端と入れ替える ここで、i…

atcoder.jp 解法 制約的にも桁DPがしたくなる。 そこで次のDPを考える。 dp[i][j] ← 下からi桁目までみた時、13で割った数がjであるような場合は何通りあるか 上からi桁目としてもいいが、計算が楽なので下から見ていくことにした。 次のように遷移する。 こ…

atcoder.jp 解法 それぞれの鍵を買うか否かの選択をM回することになるので、愚直に全探索しようとするとO(2M)になるが、制約的に時間が足りない。 そこでDPができないかを考えてみる。 愚直解がO(2n)になってしまう時、DPを使うと無駄な計算を省いて高速化で…

atcoder.jp 解法 愚直に解こうとするとO(2N)で絶対間に合わない。 Aはmax、Bは総和が条件として示されているため、A[i] ≦ 5000という制約が気になる。 この制約があることで、Bの和が5000より大きい数になるような集合は考えなくて良いことになる。 Bの要素…

atcoder.jp 解法 絶対値を外すことができれば、(i, j)と(i', j') を分離できるので計算しやすくなる。 そこで、i ≧ i'かつ j ≧ j' という条件をつけることにする。 これで絶対値の中が必ず0以上になるため、絶対値を外して計算できるようになる。 i < i' か…

atcoder.jp 解法 都市から都市への移動を繰り返すという行為が、DPで遷移するというのに酷似しているため、DPをしたくなる。 次のようなDPを考える。 dp[i][j] ← i日目に都市jにいる旅の仕方は何通りか ただ問題文通りにK回、N個の町から通れる道を使って遷…

atcoder.jp 解法 問題を簡単に言い換えると、同じ種類のコンテストには連続でしか出場できないという条件を満たす、コンテストへの出場の仕方は何通りですか？ といった感じになる。 DPで解くことを考えてみる。 どの種類のコンテストへの出場経験があるか、…

atcoder.jp 水diff後半にしては簡単？ D問題になってたらdiffが下がりそう。 解法 次のようなDPを考えます。 dp[i][j][k] ← (i, j)にいる時、既にi行でk個のアイテムを拾った場合の最大値 また、二次元配列Gを次のように定義します。 G[i][j] ← (i, j)に落ち…

atcoder.jp 解法 問題を見てすぐに下のようなDPが思い浮かんだ。 dp[i][j] ← (i, j)へ行く場合の数 ただ、愚直に遷移しようとすると1つのマスにつき、H+W回ぐらいの遷移が必要になるのでこれでは間に合わない。 手を動かして、DPテーブルがどのような値をと…

atcoder.jp bitDPについて初めて学んだのでメモしておく。 bitDPとは？ 下の記事たちがわかりやすい。 algo-logic.info qiita.com 解法 巡回セールスマン問題であることが制約や問題名から読み取れる。 この問題の説明は下の記事でもされているので省く。 al…

atcoder.jp 解法 参考: 桁DPについて nizi-24.hatenablog.com 桁DPをしよう。 dp[i][smaller][k] ← i: 上から何桁目まで確定しているか、smaller: 未満フラグ、k: 今までに何個0以外の数字が登場したか 遷移するときには、0かどうかで場合分けすればよい。 …

atcoder.jp 桁DPの問題。初めて桁DPについて学んだので記事にします。 桁DPとは？ ・N以下の自然数で条件を満たすものは何通りか？ ・N以下の自然数で条件を満たすものの中で最大のものはいくつか？ みたいな問題で活躍するアルゴリズムです。 説明は少し複…

atcoder.jp 解法 ぱっと見、部分和問題かなと思うが、O(N2)になってしまうため間に合わない。 他の方法を考えてみると、 ・なぜか区間が与えられている ・Kが小さい ・区間は共通部分を持たない と怪しい部分がたくさんあることに気づく。 区間を利用して高…

atcoder.jp 解法 再帰によって条件を満たすそれぞれの確率を求めようとすると、3100以上の計算量が必要になる場合がある。 愚直に解こうとすると指数時間になってしまう場合、DP(メモ化再帰)が有効になる場合は良くある。 そこで、3つの硬貨の数の取りうる場…

atcoder.jp LIS問題という有名問題を少し変えた問題です。 LIS問題について 最長増加部分列(LIS)問題は、昇順(または降順)となるような部分列は最長でいくつ作れるか？という問題です。 O(N2)のDPが最初に思いつきましたが、これでは間に合いません。 有名問…