桁DPについて
はじめに
これは桁DPに入門した私のメモ程度の記事になります。プロによる解説は
あたりを参照することを推奨します。
※この記事は書きかけになります。随時更新します。
桁DP
桁DPは「整数N以下の数に対してある条件xが成り立つ場合」の個数の数え上げによく使用できる気がします。着想としては、整数Nに成り立つ条件を桁ごとにまとめて考えることで、Nが非常に大きい場合でも計算が可能になります。
簡単な例から考えていきます。とーらすさんの記事にもありますが、「N以下の整数の数」を桁DPで求めてみましょう。DP遷移に必要な状態は、現在着目している桁iに関する情報と、上からk桁目まで考えているときにすでにもとの整数Nを超えているかいないか。という情報です。
桁DPを考えるときにある桁まで決まっていて、次の桁の数を考えるとき、無条件にすべての数を決められるわけではありません。たとえば、もともとの数が1234と与えられていて1234以下の数を数え上げる時、今2桁目まで決まっているとします。すなわち12??という状態です。この時、3桁目の?に入れることができる数字はもともとの3桁目の数である3までです。4,5,..はもともとの数よりも大きくなってしまうので、数え上げてしまうと過剰に数えていることになります。3桁目には0,1,2,3の4つの候補まで遷移の対象とすることがシンプルな数え上げ方です。
先程は12??という状況を考えましたが、逆に02??という場合であればどうでしょうか。?にどんな数字をいれても1234より02??のほうが小さくなっています。この場合は3桁目に任意の数を入れてももとの数を超えることはありません。このようにk桁目の数を考えるときに、k-1桁目でもとの数とぴったり同じなのか、それもとすで下回っているのかということを判断することが桁DPでは重要になります。
実装例
上の例「N以下の整数の数 (0<=N<=1015)」を求めてみます。
DPの実装方法としては、上のプロ達のブログで書かれているような配列を使用した実装とメモ化再帰によるものがありますが、ここではメモ化再帰による実装を紹介します。
メモ化に必要なテーブルは [桁数] と [現在元の数字とぴったりかどうか] の2つの状態を保持するテーブルです。 再帰する時に呼び出す条件に関しては以下のコード内にコメントとして記載しました。
public class Sample { // 整数 N を文字列として保持 static char[] s; // メモ化テーブル static long[][] memo; public static void main(String[] args) { // input Scanner in = new Scanner(System.in); s = in.nextLine().toCharArray(); // メモ化テーブルの事前準備 int len = s.length; memo = new long[len+1][2]; for (long[] v : memo) { Arrays.fill(v, -1); } // 桁DP long ans = rec(0, 1); System.out.println(ans); } static long rec(int i, int tight) { if (memo[i][tight] >= 0) { return memo[i][tight]; } // すべての桁を遷移したときに、条件xが成立する場合を数えます。 // 今回の場合は、数に対する条件はなくすべての数を数えます。 if (i == s.length) { return memo[i][tight] = 1; } // 現在着目している桁の数が何か int d = s[i]-'0'; // DP遷移 long ret = 0; // i-1桁までが元の数字とぴったり同じ場合は tight = 1 なので、dまで // そうでない場合は、任意の数字まで遷移できるので 9 まで for (int e = 0; e <= (tight == 1 ? d : 9); e++) { // 次の遷移を考える時、tightが1で今回選択しているeがもとの数字dと同じ場合は // ぴったり同じなのでtight = 1 そうでない場合は小さいので tight = 0 ret += rec(i+1, tight == 1 && d == e ? 1 : 0); } return memo[i][tight] = ret; } }
