2017/10/05の精進

とりあえず色んなテクニックの練習問題をやっていこうということで、はまやんさんの問題集(競技プログラミング練習問題集 - はまやんはまやんはまやん)をやることにした

今日は動的計画法問題まとめの入門問題を埋めたけど、さすがに簡単だった

明日は木DPをやりたい

以下、答え(メモリが足りないときは再利用DPする)

・AOJ 0-1ナップサック問題

そのまんま dp[i][j]=i番目までの品物から重さがj以下となるよう選んだときの価値の最大値

・yukicoder No.458 異なる素数の和

あらかじめ20000以下の素数を列挙しといて

dp[i][j]=jをi番目までの異なる素数の和で表すときの、和の回数の最大値

・ABC 015 高橋くんの苦悩

dp[i][j][k]=i番目までのスクショからj枚以下・幅合計k以下となるよう選んだときの重要度の最大値

・ABC 054 Mixing Experiment

dp[i][j][k]=i番目までの薬品からタイプAがjグラム・タイプBがkグラムとなるよう選んだときの価格の最小値

・yukicoder No.472 平均順位

dp[i][j]=i番目までのコンテストでj問解いたときの順位の和の最小値

・yukicoder No.561 東京と京都

dp[i][j]=i日目に場所j(j=0:東京 j=1:京都)にいるときの利益の最大値

・yukicoder No.4 おもりと天秤

dp[i][j]=i番目までのおもりから重さがjとなるように選べるか

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

dp[i][j]=i番目までのスイッチからXがjとなるように選べるか

・ABC 011 123引き算

dp[i][j]=i回目までの処理でNをjにすることができるか

・ARC 075 Bugged

今までと同様に和をある数に出来るかDPで調べてもいいが、Σsが10の倍数でないならそれが答え、Σsが10の倍数なら10の倍数でない最小のsを引いたものが答え、ないなら0とわかってしまう

・TDPC コンテスト

dp[i][j]=i番目までの問題から得点がjとなるように選べるか

・yukicoder No.44 DPなすごろく

フィボナッチ数列 dp[i]=iマス目までの行き方が何通りか

・yukicoder No.314 ケンケンパ

dp[i][j]=長さi・最後にj回ケンが並んでいるケンケンパが何通りか