ABC242 C - 1111gal password から見るDPの話
CはDPのC（え？）
お久しぶりです． 最近AtCoder ABCのC問題にDPがさらっとでてくるようになってきていて，競プロ界隈のレベルの上昇度を感じます．Nafmoといいます．
古の競プロerを自称しているNafmo(2017-2018)ですが，最近落ち着いたのでまたやろうかなと思ってやっています．リハビリ状態というのと，全盛期でもできたか怪しいDPを解いて楽しくなったので記事を書きたいと思います．
【注意】久々の記事なので温かい目で見守ってください．間違いを見つけた場合は優しく教えていただけると大変助かります．よろしくお願いします．
(私マンボウなので鋭くなくても雑なまさかり受けると再起不能になるので優しくお願いします....ﾕﾙｼﾃ)
なぜ記事を書こうと思ったのか
単純に私が試行錯誤して解けた経験を共有することで，他の誰かの役に立ってほしいと願うからです(自己満ですね)
ABC242 C - 1111gal password
問題概要
この条件を満たす整数Xの個数を998244353で割ったあまりは？
条件(ちょい雑)
- N桁整数
- 整数Xのすべての桁は1-9
- 整数Xはある桁を見た時，その次の桁との差の絶対値が1以下
正解解法への過程(Nafmoの場合)
なんとなく書いていきます．
最初は全探索から考えよう
- 深さ優先探索で各桁3種類ずつ遷移しようとした
- つまり，その桁が3なら，次の桁は2,3,4というような感じで
- N桁潜れたらans++して行く
- 計算量爆発(
)
- 桁ごとに選択肢が3倍になっていくのでそれはそう...
- 全探索だしね
計算量改善しよう
一桁ずつ決めていくから，前から順番に数えていけば良さそう！
今，桁目を見ているとします．
を
桁目が
の時の条件を満たしている整数の数だとすると，
桁目は
個だけあることになり，一つ前の状態がわかっていれば求めることができる事に気づきました(添字がはみ出た場合は0とします)
したら後はループを回せばいいよねってことで以下がソースコード
// X:次の状態,x:前の状態 ll X[]={0,1,1,1,1,1,1,1,1,1,0}; for(int i=0;i<N-1;i++){ ll x[11]; REP(k,11)x[k]=X[k]; X[1]=(x[1]+x[2])%MOD; X[9]=(x[9]+x[8])%MOD; for(int k=2;k<=8;k++){ X[k]=(x[k-1]+x[k]+x[k+1])%MOD; } } // X[1]~X[9]の和が答え
配るDPともらうDP，メモ化再帰と漸化式ループDP
なにそれという方向けに，けんちょんの記事を
今までの私はメモ化再帰しか書けませんでした．
しかし，この問題をACしたときはナチュラルに漸化式のような考え方ができています．(公式解説はこれを二次元配列にしたものなので...)
これ，精進していない謎の成長でした．メモ化再帰で配るDPが書きにくい(※要出典*1 )(個人の感想)から生まれたものな気がしています．
どういうことかと言うと，自分のメモ化再帰の癖で return dp[i-1][～～～]+dp[i-1][～～～] のような1個前(複数前)の状態から求めたい結果を導くというように書く癖があります．これが100%悪いとは思っていませんでしたが，これだと今回のような配るタイプは難しく感じました．
実装してみてわかったこともあって，配ったりもらったりを漸化式立てて脳死ループを回す方が，再帰の境界処理と遷移を考えるより楽ということです．式立てられれば終わりなので...
先ほど貼った記事の漸化式ループDPのメリットが出てますね．できるようになりたい！という感想セクションでした．
話題になった桁DPと言われているもの
今回の問題はそんな難しく考えなくても，注目している桁とその前の桁だけ見れば良いので大丈夫だったりします．なのでこの問題に限っては，桁DPという名前を意識しなくてもいいのかなと思います．
でもコンテスト終了時に名前を見るときになりますよね．(？？？「私，気になります」) そこでなぜ名前が上がったのかを考えてみました．
考え方が似てたからなんだろうな(ド直球)というのと，桁(に注目して操作する)DPと言いたかったのかな？と思いました．
桁DPってなんだよという方は，私はこのサイトが分かりやすかったので参考までに．
以下のような分け方で中学受験の問題解いた記憶有りませんか？私はあるのですっと入ってきました．
つまりどういうことかと言うと，1桁ずつ決めていく過程で，ここがこの数なら残り全部オッケーっていう場合と，そうじゃない場合を分けて考えるということをしたいという話です．未満(smaller)フラグについてもわかりやすかったですね．個人の感想ですが...
参考2 ココも好きでした．合わせて見てみるといいかも・・・？
桁DP(Digit DP) を考え方から問題例まで徹底解説！ | アルゴリズムロジック
さて，話をもとに戻します．
私の考えとしては，上位陣(？)はこの問題は桁ごとに操作をして行くことを伝えて桁DPといえば解説が住んじゃうような問題だったからそうなったのかなと思いました．
今の私(緑)には桁DPの理解よりも自分の実力適性帯を早く解ければそれでいいと感じました．
問題から見た振り返りおしまい．
終わりに
この記事は大学の仲間に「桁DPわからんから説明してほしい」とこの問題の出題後に言われたから書きました．25日遅れですよ！ ...ごめんなさい．定期試験とか挟まったし(言い訳やめてください)
桁DPの解説をしてほしいという話だったのに結論が桁DPとかいいからこの問題が解けるDPの考え方がわかればヨシ！(画像略)という結論なの悲しいですね．
気が向いたりしたらまた書きます．面白かったりなにか得るものがあったら嬉しいですし，それをTwitterに書いてくれたりStar付けてくれたりするとモチベが上がるのでまた書く可能性が上がります．よろしくお願いします．頑張って2018全盛期の自分を超えたい！これからも競プロがんばります！
それではまた．(1時間もかけたのやばいな，普通に1問解けるやんけ)
*1:でもけんちょんの記事にはそう書いてある
