駆け出し出遅れプログラミング初心者の日記

 初めましての方は初めまして、鳥居です。

今回は桁DPというやつにチャレンジしてみたいと思います。(実は記事作成途中にデータが吹っ飛んでしまい、一からまた書き直しているところです。…完全に自業自得orz)

https://atcoder.jp/contests/abc154/tasks/abc154_e

まず入力ですが、int型どころかunsigned long long型でもオーバーフローしそうなので、string型で受け取っておくことにします。(C++以外の言語ではこれ以上の値でも受け取れる型があるようなので、それを使ってもいいかもしれません)

さて、肝心の解き方ですが…どう解くんでしょう？(;'∀')(ｵｲｵｲ)

自力で解くのはあきらめて(はえーよ)、他の方の桁DPについての記事を参照してみたいと思います。

https://torus711.hatenablog.com/entry/20150423/1429794075

「ある整数N以下の整数で、かつ特定の条件を満たす値を求める」ときに使えるのが、桁DPというものっぽいです。まさに今回のような問題ですね。

そして具体的な方法としては、上の桁の値から見ていくDPを考えていくようです。こういったときに桁ごとの値を参照しやすいといった面でもstring型で値を受け取ったほうがいいというメリットがありそうですね。

そしてdpを回していくわけですが、どうやらパラメータとして

・上から見て行ってすでに決まっている桁数

・求めたい値の条件(この場合だとゼロでない値の数[1~3])

そしてもう一つ

・その桁の次に小さい桁を見たときに、その桁の値がすでに決まっている桁と合わせて入力として与えられた値未満かその値と同じか

というフラグが必要になってくるようです。(相変わらず自分で書いてても意味が…(;'∀'))

例えば入力として12345が与えられ、上から二けた目までの数(12~)までが決定しているとして、

・３桁目が3未満だった場合には、それより下の桁は何を選んでもよい。

・3桁目がちょうど3だった場合には、それのさらに一個下の値は4までしか選べない

・3以上の値を3桁目に入れるわけにはいかない

ので、このようなフラグをまえもって準備しておくと後の計算が楽になるっぽいです。

そして、上から順々に値を埋めていって最後に求められているクエリを提出すればよい…らしいです。(初心者なので自信ないorz)

桁DPについて更に知りたい方は(私が書いたこんな残念な記事より)ほかの方の記事を参照してください。(一番下にあげたmaspyさんという方の解法は今回紹介したものとはまた別の解法となっているようなので、特にご覧いただくのをおすすめします。)

http://drken1215.hatenablog.com/entry/2019/02/04/013700

https://maspypy.com/atcoder-%e5%8f%82%e5%8a%a0%e6%84%9f%e6%83%b3-2019-02-09abc-154