yukicoder No.319 happy b1rthday 2 me

この記事は読者が桁DPを知っているという前提で書かれています。桁DPがわからないという方はこちらの記事へ。

の和が求めたい値になる。それぞれの求め方を順に説明する。

という関数を作れば、f(B)-f(A-1)で計算できる。f(N)の計算は次のような桁DPをすればいい。

dp[ 決定した桁数 ][ N未満確定か ][ 末尾が1か ][ 12の個数 ] := この条件を満たす数の総数

遷移方法は「末尾が1である数に2を付加すれば12がひとつできる」ということを考えると分かる。

****1に2****を繋ぐと12が生まれる。 2つの数の差が1なので最上位桁の数字は一致しており、実は2***1と2***2の組になっている。そのため2***1の形の数の総数を数え上げればいい。

という関数を作れば、g(B-1)-g(A-1)で計算できる。 g(B)ではなくg(B-1)を計算するのはなぜかというと、Bが2***1の形だったとしても次の数がなく12が生まれないからである。

g(N)の計算も桁DPでできる。最上位桁が2であるという条件を考えるのにleading zeroの情報が必要なため、次のようなDPになる。

dp[ 決定した桁数 ][ N未満確定か ][ leading zeroを抜けたか ] := この条件を満たす数の総数

遷移方法は次の2つを考えると分かる。

なお、例外的に1,2は12を生むので微調整が必要。

似たようなDPを2回書くのは面倒だったので、共通部分を使いまわした。

ABC029 Dみたいに解けるのは分かるんだけど、結局思考停止して桁DPしてしまった。