EDPCで桁DPやってみたけど,なんかよく分からなくて,Huluでアニメ見ながら考えたけど,やっぱりよく分からなくて,かつ><ぱーさんの動画見て解説写経してみて少し分かった気になって,他の桁DP自分で通さないとな,っていう気分になってやってみたけど答え合わなくて,他の人の解説記事読んでみたけどよく分からなくて,全ての提出から添字3つもった桁DPを書いてる人探して読んでみたけど良く分からなくて,仕方ない,手元動かしながらかんがえるかって思って,でもそれは明日でいいやって言って寝て.起きて,風呂入ってパスタ食ってパスタ食って,手動かして,答え合わなくて,ちょっと考え直してやっとのことでACした問題について書く
まえがき
今日はタイトルが長いです.ライトノベルを意識してみました.
いや,嘘です.本当は前書きをあれにしようとおもったんだけど,何となくタイトルにしてみた.
ライトノベルって言う割にはタイトルはライトじゃないもの,結構ありますよね.
ところでこの前「,や.を日本文でも使うやつwww」みたいな話を見ました.
俺は普段日本語の文をペンで書く時は「、や。(句点読点)」を使いますが,PCを使ってるときは「,や.」にしています(どちらも半角).
理由は,論文云々とかって言うよりも,「Markdown書くとき(このブログもそう)に,いちいち日本語入力→英語入力にして半角にするのがめんどくさいから」ですかね.例えばmarkdownでは改行するときに<br>
って書かなきゃ行けないんですけど,これ「大なり<と小なり>」を日本語入力でやるとデフォルトだと全角になっちゃうじゃないですか.＜br＞だと改行として受け取ってくれないんですよね. まあ,そんな感じなノリかなあ(伝わらないならいいや)
あとがきは日本の国歌を文字起こししただけです.
今日解いた問題
ABC007 D-禁止された数字
[桁DP,MOD使わないぴょん,遷移4通り?,もらうDP]
K以下の整数の中で,4か9を含んでしまう整数は何通りありますか?
まぁ,この問題を解くタイミングというのは,EDPCの桁DPをやって,どっかしらの解説読んで,「う~ん,桁DPやってみたけど自信なさすぎる…他の類題解いてみるか」ってときぐらいなんじゃないですか(まあ僕のタイミングですが)
EDPCの解説動画,かつ><ぱーさん(名前伏せてるつもり)の動画がおすすめな気がします.毎回コード1から(多分)書いてるし,動画10分程度でお手軽だし,後なんかコード書くテクニック的なのを感じながらやれる気がする(知らんけど)
とりあえず提出ACコード(コメント付き)
とりあえず,B以下の数字で4,9を含むモノの数-(A-1)以下の数字で4,9を含む物の数っていうのが解ると思います.
ちなみに,なんか変な言葉(とりあえずだとか,気がするとか,はぁ,とかクソが)とかっていう言葉を多用してるのは,最近そういう気分だからです.
ああ,話がずれた.ちなみに今は右のモニターでマツコ会議みながら記事書いてるよ.
他の人の解説見ると,forの中が結構簡潔そうなコードがある(気がします)けど,今回僕は,「桁DPやってみたけど,よう分からんかったな…,丁寧丁寧丁寧に書いてとりあえずACしてみるか」っていう気持ちでやったので,コードは長いです.
方針は
- 4つある状態について,一つずつ書いていこう
という感じですかねえ…
まずfunc(K)を作成しました.これは,K(Kは文字列ではあるが…)以下の数字で4,9を含むモノの数を返す関数です.
こうすることで,func(b) - func(a-1)が答えでしゅ(あ,噛んじゃった♡)
さて,funcの中身を見ていこう.
ll dp[20][2][2]; int n; ll func(string K){ n = K.size(); rep(i1,20)rep(i2,2)rep(i3,2)dp[i1][i2][i3] = 0; dp[0][1][0] = 1; // dp[i1][i2][i3] := 上からi1桁目まで見た //状態がi2である([1] := 数字がK未満であることが確定していない //状態がi3である([1] := 4か9を含んでいる)
とりあえずdpテーブルを0埋めします.
dp_i1_i2_i3は,上からi1桁まで見たとき,状態がi2,i3である時の数字の個数です.
i2が2通り,i3が2通りあるので,2かける2=4で,先程に4つある状態について一つずつ書いていこうといいました.
- 状態i2は, 0なら,i1桁目まで決めた時点で既に数字がK未満,1ならK以上(っていうか,i1桁目まで数字がKと一致)(この日本語は,まぁ他の人の日本語とかと比べて分かりやすいものを採用してください.多分どれも同じこと言ってると思う)
- 状態i3は,0ならi1桁目まで見た時点で,4,9が数字に入っていない.1なら4,9が有り.
i2_i3の組は(0,0)(0,1)(1,0)(1,1)の4つ有りますね.めんどくさいけど全部確認しましょう
(0,0)のとき
K未満が確定
4,9は含まれていない
(0,1)のとき
K未満が確定
4,9が含まれている
(1,0)のとき
K以上(K未満であることが確定していない)
4,9が含まれていない
(1,1)のとき
K以上(K未満であることが確定していない)
4,9が含まれている.
こうやって書いた上で,更に更に,ここから書いていくコードを理解するためには,図が必要になります
ちなみに以下のようなコードを書きます
for(int i1 = 1; i1 <= n; i1++){ int digit = K[i1-1] - '0'; for(int k = 0; k < 10; k++){//i1桁目をkにするときの遷移書く // dp[i1][i2][i3]のi2,i3が(0,0),(0,1),(1,0),(1,1)の順にやっていこう // dp[i1][0][0]への遷移を書く (K未満確定,4,9無し) if(k != 4 && k != 9){ dp[i1][0][0] += dp[i1-1][0][0]; if(k < digit) dp[i1][0][0] += dp[i1-1][1][0]; } // dp[i1][0][1]への遷移を書く (K未満確定,4,9有り) dp[i1][0][1] += dp[i1-1][0][1]; if(k == 4 || k == 9){ dp[i1][0][1] += dp[i1-1][0][0]; if(k < digit){ dp[i1][0][1] += dp[i1-1][1][0]; } } if(k < digit) dp[i1][0][1] += dp[i1-1][1][1]; // dp[i1][1][0]への遷移を書く (K以上,4,9無し) if(k == digit && k!=4 && k!=9){ dp[i1][1][0] += dp[i1-1][1][0]; } // dp[i1][1][1]への遷移を書く (K以上,4,9有り) if(k == digit){ dp[i1][1][1] += dp[i1-1][1][1]; if(k == 4 || k == 9){ dp[i1][1][1] += dp[i1-1][1][0]; } } } }
めっちゃ長いね.(丁寧丁寧丁寧に書いたので)
ちなみにコメントをなくすと
for(int i1 = 1; i1 <= n; i1++){ int digit = K[i1-1] - '0'; for(int k = 0; k < 10; k++){ if(k != 4 && k != 9){ dp[i1][0][0] += dp[i1-1][0][0]; if(k < digit) dp[i1][0][0] += dp[i1-1][1][0]; } dp[i1][0][1] += dp[i1-1][0][1]; if(k == 4 || k == 9){ dp[i1][0][1] += dp[i1-1][0][0]; if(k < digit){ dp[i1][0][1] += dp[i1-1][1][0]; } } if(k < digit) dp[i1][0][1] += dp[i1-1][1][1]; if(k == digit && k!=4 && k!=9){ dp[i1][1][0] += dp[i1-1][1][0]; } if(k == digit){ dp[i1][1][1] += dp[i1-1][1][1]; if(k == 4 || k == 9){ dp[i1][1][1] += dp[i1-1][1][0]; } } } }
これくらいのコードになります(あんまり変わらないね)
じゃあ,状態遷移図書いてみようか.
あ,まって,状態遷移図書く前に,(理解の手助け??)前提条件的なやつを
- K未満が確定しているならば,i1桁目を決めることでK以上になることは絶対にない
- 4,9が含まれているなら,i1桁目を決めたことで4,9を含まれていない状態に遷移することは絶対にない
これ,実際は手元で紙に書いたやつを,今日は珍しく頑張ってdiagrams.netってやつ使って頑張って書きました.この記事読んで桁DPちょっとでも理解できたやつは感謝しろよな.感謝しろよな.
遷移の図を書くときに意識することは,各状態(四角の中に状態が記されている)から,他の状態へ遷移(移動)するときに,kが0から9までの値であるときに,その全てを考慮出来ているか.ということを意識しながら書いていきます.
状態(i2,i3)=(0,0)のときを例に取って示しましょう.
まず,四角のなかに(0,0) K未満確定,4,9無し と書く
(0,0)の状態から,どの状態へ遷移する可能性があるのかをかんがえる.
考えた結果,「未満4,9無しから未満4,9無しへの遷移」と「未満4,9無しから,未満4,9有りへの遷移」がある
K未満が確定しているなら,k=9でも8でも7でも…Kより大きくなることはないので,捨てるへの遷移はない
遷移が二通りで有ることがわかったので,(0,0)への矢印と,(0,1)への矢印を書く
kがいくつであるときに,その方向へ遷移するのかを考えて,矢印の近くに書く
未満49無しから未満4,9無しは,kが4でも9でも無いときなのでk=0,1,2,3,5,6,7,8のとき,と書いておく
未満49無しから未満4,9アリは,kが4か9のときなので,k=4,9と書く
kが0~9全ての値について考慮出来ているかをかんがえる
(0,0)への矢印は4,9以外,(0,1)への矢印は4,9があるので,0~9全て考慮されているのでおk
まあ,こんな感じの手順で,まず状態1つに対して,他の状態への矢印と,kがいくつのときにその状態へ遷移するのかを書いていく.
そんな感じで,状態(0,0)から(0,1)(1,0)(1,1)への矢印を書いていって(絶対に遷移しない相手には書かなくていい)全ての状態から矢印が発信するようになったら,次はコーディングです.
桁DPは初心者なので,今回は丁寧丁寧丁寧に書いていきます.
といっても,状態遷移表をコードに起こしていけばよいのだ.
今回も,(i2,i3)=(0,0)を例に取ってやっていきましょう.
必要な部分だけ取り出してみました.(左下の(1,0)から(1,0)の矢印は,今は見なくて良い)
dp_i1_0_0を決めるときにやることは,状態(0,0)へ向かっている矢印から,条件を満たしているときにもらう ということです.
よって,次のようなコードを書きます.
for(int k = 0; k < 10; k++){ if(k != 4 && k != 9){ dp[i1][0][0] += dp[i1-1][0][0]; if(k < digit) dp[i1][0][0] += dp[i1-1][1][0]; } }
これを,他の部分についてもやっていった結果が,
//状態がi3である([1] := 4か9を含んでいる) for(int i1 = 1; i1 <= n; i1++){ int digit = K[i1-1] - '0'; for(int k = 0; k < 10; k++){//i1桁目をkにするときの遷移書く // dp[i1][i2][i3]のi2,i3が(0,0),(0,1),(1,0),(1,1)の順にやっていこう // dp[i1][0][0]への遷移を書く (K未満確定,4,9無し) if(k != 4 && k != 9){ dp[i1][0][0] += dp[i1-1][0][0]; if(k < digit) dp[i1][0][0] += dp[i1-1][1][0]; } // dp[i1][0][1]への遷移を書く (K未満確定,4,9有り) dp[i1][0][1] += dp[i1-1][0][1]; if(k == 4 || k == 9){ dp[i1][0][1] += dp[i1-1][0][0]; if(k < digit){ dp[i1][0][1] += dp[i1-1][1][0]; } } if(k < digit) dp[i1][0][1] += dp[i1-1][1][1]; // dp[i1][1][0]への遷移を書く (K以上,4,9無し) if(k == digit && k!=4 && k!=9){ dp[i1][1][0] += dp[i1-1][1][0]; } // dp[i1][1][1]への遷移を書く (K以上,4,9有り) if(k == digit){ dp[i1][1][1] += dp[i1-1][1][1]; if(k == 4 || k == 9){ dp[i1][1][1] += dp[i1-1][1][0]; } } } }
こんな感じです.丁寧に,丁寧に,丁寧に頑張ってみました.(ちなみに,捨てる,への遷移は,考慮しない,ってことなので特に何も書かなくていい)
ちなみに,最後に答えが合わなかったときは,
(1,0)から(0,1)への遷移の矢印を忘れていました.
(つまり,4,9がなくてK未満が確定していないところから,K未満が確定して,4,9が有りになる.ところへの遷移を忘れていました.)
終わりです.
あとがき
はじめるのが遅いって別に誇ることじゃないけど,
はじめるの遅かったけどもうこんなに強くなった!!みたいなことっていいたくなるよね
なんか,プログラミングやり始めるのが遅ければ,特に勉強頑張っていたわけでもないし,なんなら今もそんなにプログラミングやる気ないし,大学もやる気ないしって感じなんだよね(実際なんもやってないんだけど)
で,やりはじめるの遅いのは言い訳でしか無いけど,「プログラミングって個人で学べるなら大学入る前に教えてくれよ」っていいたくなる.
で,特にやる気もないから大学でやりたかったのはこういうことじゃないんだよな…別にディジタル信号処理とか知らねえよ,変換ってなんだよ.って言って学ぶの面白くないとか言ってる.
なんか別に特に頭の中整理して書いてるわけじゃないからタダの思考の垂れ流しだけどね.
で,なんか,やりはじめるのが遅いし,やる気もないし,めんどくさがってるような日々を最近行なってるんだけど,
俺ぐらいのやる気のなさ(もしくは俺ぐらいのやる気があって)頭よくなくて(もしくは俺ぐらい頭がよくて),競プロやってる人に対して,
うわあ,なんか桁DPやってみたけどよくわからないなあ,いろんな記事とか(3分ぐらい)読んでみたけどよくわからないなあ…はァ…手元動かすのめんどくさいなあ…
っていう人に対して(別にそういう人だけじゃないけど),あ~,なんか,ちょっとこの記事分かりやすいかも.みたいな感じで解説出来たらいいなあって思ってちょと頑張って自力でACしてみた.
願わくば,この記事が誰かの役に立つことを願う…
誰の役にも立たなかったら,水色行ったことあるぐらいの人間ならこんなの余裕で理解できるww理解できないのはお前(にぼし)だけwwwって感じで悲しい気持ちになってしまう.
以下は毎回記事に貼っているテンプレート
基本的に読書はTwitterで絡みのある人だけだと思いますが、僕のブログだけ見てるって人もいるかもしれないので、一応自己紹介っぽいことをしている記事を貼っておきます
