はまやんはまやんはまやん

hamayanhamayan's blog

競技プログラミングにおける入門動的計画法問題まとめ

基礎: http://hamayanhamayan.hatenablog.jp/entry/2017/02/27/021329
応用: http://hamayanhamayan.hatenablog.jp/entry/2017/02/27/021423

動的計画法は結構練習しないと難しいです。
動的計画法がよく使われる条件は以下の通りです。

  • 数え上げ(mod 10^9+7)
  • 最小値・最大値を求めたい

これ以外にも本当に色んな目的で使われます。
基本は説明しないので、他で勉強しましょう。

雑多な事項

  • ループで書くか、再帰関数かというのがありますが、どっちかの書き方の方が書きやすい(というか書けない)とかがあったりするので、どちらも書けるようになるのがオススメです。
  • dpの配列の作り方によってループ・再帰での書きやすさが違ってきたりします。
  • dpの領域を圧縮するために、再利用するとかmapを使うとかあります
  • dpの更新にデータ構造を利用したりします

問題

最大値・最小値系, ナップサック系
dp[] := その条件下での最大値・最小値

yes/no系
dp[] := その条件下でのtrue/false

組合せ数を数える
dp[] := その条件下での組合せ数






以下、dp構成と解法紹介

最大値・最小値系, ナップサック系

yukicoder No.458 異なる素数の和

http://yukicoder.me/problems/no/458
dp[i][j] := i番目の素数まで使ってjを作る素数の個数の最大
解答: http://yukicoder.me/submissions/154257

ABC 015 D. 高橋くんの苦悩

http://abc015.contest.atcoder.jp/tasks/abc015_4
dp[i][j] := i枚目までで幅がjで、重要度の最大値

ABC 054 D. Mixing Experiment

http://abc054.contest.atcoder.jp/tasks/abc054_d
dp[i][j][k] := i番目まででAがjグラムBがkグラム用意する値段の最小値

yukicoder No.472 平均順位

http://yukicoder.me/problems/no/472
dp[i][j] := i番目のコンテストまでで累計j問解いたときの順位の最小値
dpテーブルは使いまわさないとMLEする

yes/no系

Typical DP Contest A. コンテスト

http://tdpc.contest.atcoder.jp/tasks/tdpc_contest
dp[i][j] := i問目まで解いて得点がjを作れるか

yukicoder No.4 おもりと天秤

http://yukicoder.me/problems/no/4
dp[i][j] := i個までで重さjを作れるか

yukicoder No.183 たのしい排他的論理和(EASY)

http://yukicoder.me/problems/no/183
dp[i][j] := i個まででX=jを作れるか

ABC 011 C. 123引き算

http://abc011.contest.atcoder.jp/tasks/abc011_3
dp[i] := iに到達可能か

ARC075 C. Bugged

dp[i][j] := i個までの問題を使って、合計得点をj点にできるか

組合せ数を数える

yukicoder No.44 DPなすごろく

http://yukicoder.me/problems/no/44
dp[i][j] := i回目にjマス目にいる組合せ
ループ:
再帰:

yukicoder No.314 ケンケンパ

http://yukicoder.me/problems/no/314
dp[i][j] := 長さiで最後に続いたケンがj回の組合せ
ループ:
再帰: