動的計画法の練習
動的計画法はなかなか実装が慣れません。
一度時間を取ってちゃんと勉強してみます。
問題
この問題で練習します。
atcoder.jp
人は基本リンクを踏まないのでスクショを置きます。
解法その１
設定されうる暗証番号がたかだか103通りなのでそれを利用して解きます。
ラッキーナンバーSから暗証番号"ijk"が作れるかどうかのループを1000回回します。
自分もこの解法で解いたコードを提出しました。(提出コードのリンク)
解法その２
まず多次元配列を作ります。
bool dp[pos][len][current];
bool型となっています。
これはN桁のラッキーナンバーSを、
あるところまで走査した結果（ pos ）、
何文字か拾ってきて（ len ）、
ある文字列（ cuurent ）を作れるのかどうかをtrue/falseで表します。
最後にpos = Nかつlen = 3のtrueを数えます。
この個数がSを最後まで走査して3文字拾って作れる文字列の個数となります。
今回のアルゴリズムの流れとしては
ある地点（ dp[ i ][ j ][ k ] ）から次に進める道を開拓していって到達可能な目的地の数を最後に集計するという流れになります。
つまり配列を宣言した時点では配列の中身は全てfalse、未開拓状態です。
左の原点Oから出発して右下の太線のどこか1点まで行きたいです。
経路はどのようでも構いません。行けるかどうかが知りたいです。
最後に行けた数を数えます。
とりあえず
dp[0][0][0]から始めていきましょう。
始めの状態として全ての配列の中身はfalseですが、スタート地点に立てないとなると道の開拓の仕様がないので、これはtrueとします。
これが初期条件となります。
dp[0][0][0]=true;
次に、遷移を考えます。
解説にもあるように、この動的計画法の遷移は「次の文字を拾うか」「次の文字を無視するか」の2通りしかありません。
つまり、dp[ i ][ j ][ k ]において、
dp[ i+1 ][ j+1 ][ k * 10+S[ i ]-'0' ]（次の文字を拾う場合）
[ i+1 ] ← (次の文字を見てるので当然１プラスされる)
[ j+1 ] ← (次の文字を拾うというので当然 len もプラスされる)
[ k * 10+S[ i ]-'0' ] ← (「次の文字」はS[(i+1)-1])
dp[ i+1 ][ j ][ k ]（次の文字を拾わない場合）
[ i+1 ] ← (次の文字を見てるので当然１プラスされる)
[ j ] ← (次の文字を拾わないのでそのまま)
[ k ] ← (こちらもそのまま)
の2つが次に進める道となります。
ここで「次に進める」は、そこはtrueであるということを表します。
「次に進める道をtrueとする」、これがループ毎に行う動作となります。
dp[i+1][j+1][k*10+S[i]-'0']=true; dp[i+1][j][k]=true;
また「次に進める道がある」ということは「今いる場所にも来れる」ということでもあるので、ループ中に行う動作の始めに今いる場所に来れるのかどうかを調べます。
つまり、dp[i][j][k] = falseであればcontinue;させます。
if(!dp[i][j][k])continue;
実際に
コードを組みましょう。
ループの中身から取り掛かります。
{
if(!dp[i][j][k])continue;
dp[i+1][j+1][k*10+S[i]-'0']=true;
dp[i+1][j][k]=true;
}
ここでdp[i+1][j+1][k*10+S[i]-'0']=true;についてですがこの時、jが3以上であればこの操作は無用なので頭にif文をくっつけます。
{
if(!dp[i][j][k])continue; //来れない道
if(j<3)dp[i+1][j+1][k*10+S[i]-'0']=true; //文字を拾う
dp[i+1][j][k]=true; //拾わない
}
ループの外側を作ります。
rep(i,n) //for(int i=0;i<(int)(n);i++) { rep(j,4) { rep(k,1000) { if(!dp[i][j][k])continue; if(j<3)dp[i+1][j+1][k*10+S[i]-'0']=true; dp[i+1][j][k]=true; } } }
到達できた目的地の数を集計します。
for(auto it : dp[n][3])ans+=it; //範囲for文
色々必要なものを追記して繋げます。
#include<bits/stdc++.h> #define rep(i,n) for(int i=0;i<(int)(n);i++) using namespace std; int n,ans; string S; bool dp[30009][4][1009]; main() { cin>>n>>S; dp[0][0][0]=true; rep(i,n) //for(int i=0;i<(int)(n);i++) { rep(j,4) { rep(k,1000) { if(dp[i][j][k]==false)continue; if(j<3)dp[i+1][j+1][k*10+S[i]-'0']=true; dp[i+1][j][k]=true; //デバッグ用出力 //printf("%d %d %d\n",i,j,k); } } } for(auto it : dp[n][3])ans+=it; cout<<ans<<endl; }
結論
dp難しいです。
理解できてるのかどうかは、いくつかの類題を解いてみないとなんとも言えないです。*1
精進です。
ここまでお読みいただきありがとうございました。
追記（2月11日）
類題を解きました。
atcoder.jp 解法です。
int x; bool dp[110000]; main() { cin>>x; dp[100]=true; dp[101]=true; dp[102]=true; dp[103]=true; dp[104]=true; dp[105]=true; rep(i,x) { if(!dp[i])continue; rep(j,6)dp[i+100+j]=true; } cout<<dp[x]<<endl; }
先のラッキーナンバーの問題のように
まずtrueとなる初期値を設定してその後、道を開拓していく方法がスムーズに実装できました。
メモ化再帰関数を作る方法もあるかと思いますがそれよりもシンプルなコードになっているかと思います。
類題を解きました。（その２）
atcoder.jp 解法です。
int n,m,cnt; main() { cin>>n>>m; vector<pair<int,int>> p(n+10); //fisrtに「歩けるか歩けないか（0/1）」、secondに「そこに行き着くまでの経路数」を入れる。10はバッファ p[0].second=1; //0段目に行き着くまでの経路数は１ for(auto &it : p)it.first=true; //床が壊れている段をfalseにする int t; rep(i,m) { cin>>t; p[t].first=false; } rep(i,n) { if(!p[i].first)continue; p[i+1].second=(p[i+1].second+p[i].second%mod)%mod; p[i+2].second=(p[i+2].second+p[i].second%mod)%mod; } //debug //for(auto it : p)printf("%d %d %d\n",cnt++,it.first,it.second); cout<<p[n].second<<endl; }
これについても同様に
初期値を入れて、
進める道だけ開拓して
を繰り返すだけでした。
ここらへんから「dp楽しいやん？」と思えるようになってきました。
追記その２（2月11日）
こんばんは。動的計画法完全理解者の樋口です。
本日も動的計画法の練習問題を解いたのでその記録を追記させていただきたいと思います。
提出したコードは以下のようになります。
using namespace std; int h,n,a,b; main() { //入力 cin>>h>>n; vpii v; //vector<pair<int,int>> int t=0; rep(i,n) //for(int i=0;i<(int)n;i++) { cin>>a>>b; v.push_back(make_pair(a,b)); t=max(t,a); } // 配列の宣言と初期化 int dp[h+t]; each(&it,dp)it=1e9; //for(auto it : dp) dp[0]=0; // HP0を削るに必要な魔力は当然0 //値の更新 rep(i,h+t) { rep(j,n) { //配列の外にアクセスされると困るのでif文を置く if(i+v[j].first<=h+t)dp[i+v[j].first]=min(dp[i+v[j].first],dp[i]+v[j].second); } } //debug //each(it,dp)cout<<it<<endl; //出力 int ans=INT_MAX; rep2(i,h,h+t)ans=min(ans,dp[i]); cout<<ans<<endl; }
体力iを削り切るために必要な最小魔力を配列に入れていきます。
ここでのミソは与える総ダメージ量は入力Hと等しくなくともよいということです。
最後の3行がそれについてのコードとなりますが、
与えたダメージ量がH以上、H+t未満での最小値をansとしています。
ここでいうtは一度の攻撃で与えられる最大火力、つまり一番攻撃力の高い魔法のダメージ量です。
入力が
9 2
8 1
1 10
といった場合、攻撃力8消費魔力1の魔法を2回撃つのが最適解となりますが、与える総ダメージ量は16(≠9)となります。
こんな場合でも、上記の3行によって解をしっかり取ってくることができます。
