Top

超過状態を考慮する桁DP

はじめに

桁DPは、未満フラグを状態のひとつとして持っておき、上位桁からやる方法が一般的ですが、
場合によっては下位桁からやりたくなることもあり、すると超過状態（考察対象の数より大きい数である状態）を考慮しなければいけません。
今回、この超過状態を認める桁DPの方法についてまとめました。

このページでは「講義」をし、次のページでは「演習」ができるような構成にしています。

このページで言及する内容を簡単に述べます。

下位桁からやる桁DP

繰り上がりを意識すべき場合には下位の状態が上位に伝播するので、個人的には下位桁からやりたいです。

未満フラグに相当するもの

ただ、下位桁からやるときは未満フラグが上位桁からやるときとは異なります。
「$31415$ 以下の○○の個数を数えなさい」というのを下位桁から考えてみると以下の表のようになります。

これまで
(state)		今の桁新たな状態
(nstate)		具体例
未満未満未満??012
未満同じ未満??412
未満超過超過??712
同じ未満未満??015
同じ同じ同じ??415
同じ超過超過??715
超過未満未満??099
超過同じ超過??499
超過超過超過??799

これまでで「超過」状態であったとしても、今の桁によって「未満」状態へと変化することがあり、「超過」も考える必要が出てきました。

この状態遷移の実装例をひとつ上げます。
表から見えてくる、
「新たな状態 は基本的には 今の桁 に依存するが、今の桁 が 同じ ときは これまで と一致する」
というのを使います。
未満を 0, 同じを 1, 超過を 2 としています。
未満フラグで管理しながら上位桁からやる桁DPのときとは異なり、桁の数字は常に $0$ から $9$ まで回すことに注意してください。

int cmp(int x, int y) {
  if(x <  y) { return 0; }
  if(x == y) { return 1; }
  return 2;
}

// 中略

for(int state=0; state<3; ++state) { // これまでの状態
  // 略
  for(int d=0; d<10; ++d) { // 今の桁（十進のとき）
    int nstate = cmp(d, s[i]-'0');
    if(nstate == 1) { nstate = state; }
    // 以下略
  }
}

超過フラグ

未満と同じを同一視してみます。
すると、0: 以下である, 1: 超過である、という超過フラグと見なすことができます。
さっきは超過に 2 を割り当てていましたが、1 が空いたので詰めた格好です。
実装例
for(int over=0; over<2; ++over) { // これまでの状態
  // 略
  for(int d=0; d<10; ++d) { // 今の桁（十進のとき）
    int nover = d > s[i]-'0';
    if(d == s[i]-'0') { nover = over; }
    // 以下略
  }
}

余りの計算

桁DPの問題でよくある「○○の倍数」について考えます。
「$31415$ 以下の $7$ の倍数の個数を数えなさい」というとき、上の桁からやるときは $7$ で割った余りを状態として持っておいて、
(これまでの余り * 10 + 今の桁の数字) % 7
を新たな余りの状態にします。

下の桁からやる場合は、$10^{i}$ を $7$ で割った余りを変数（p10 とします）として持っておくと、
(これまでの余り + p10 * 今の桁の数字) % 7
で新たな余りを計算できます。
p10 は初期値を $1$ とし、「$10$ 倍して $7$ での剰余を計算する」ことを桁のループごとに行えば良いです。

各桁ごとの p10 を全て事前に計算しておいて、配列に保存しておくという選択肢もあります。


超過状態のある上位桁からの桁DP

上位桁からでも超過状態を認めても良いです。
このときも、全ての桁で $0$ から $9$ まで回してください。

状態遷移

超過状態のある桁DPの下位桁からと上位桁からを比較したものを載せます。
例によって具体例で考えている数は $31415$ だと思ってください。
実装例について、省略したところではループの向きが逆になったりするんですが、
省略しなかった部分で異なるのは 12, 13 行目で、今の桁が優先されるかこれまでの状態が優先されるかの違いになります。

下位桁から
これまで
(state)		今の桁新たな状態
(nstate)		具体例
未満未満未満??012
未満同じ未満??412
未満超過超過??712
同じ未満未満??015
同じ同じ同じ??415
同じ超過超過??715
超過未満未満??099
超過同じ超過??499
超過超過超過??799

実装例
int cmp(int x, int y) {
  if(x <  y) { return 0; }
  if(x == y) { return 1; }
  return 2;
}

// 中略

for(int state=0; state<3; ++state) { // これまでの状態
  // 略
  for(int d=0; d<10; ++d) { // 今の桁（十進のとき）
    int nstate = cmp(d, s[i]-'0');
    if(nstate == 1) { nstate = state; }
    // 以下略
  }
}
上位桁から
これまで
(state)		今の桁新たな状態
(nstate)		具体例
未満未満未満120??
未満同じ未満124??
未満超過未満127??
同じ未満未満310??
同じ同じ同じ314??
同じ超過超過317??
超過未満超過990??
超過同じ超過994??
超過超過超過997??

実装例
int cmp(int x, int y) {
  if(x <  y) { return 0; }
  if(x == y) { return 1; }
  return 2;
}

// 中略

for(int state=0; state<3; ++state) { // これまでの状態
  // 略
  for(int d=0; d<10; ++d) { // 今の桁（十進のとき）
    int nstate = state;
    if(nstate == 1) { nstate = cmp(d, s[i]-'0'); }
    // 以下略
  }
}

超過フラグ？

下位桁からのときに出来た「未満と同じの同一視」は上位桁からだとできません。
これまでが未満で、今の桁が超過のときは新たな状態は未満で、
これまでが同じで、今の桁が超過のときは新たな状態は超過になります。
新たな状態が一意に決まっていないので、同一視できません。

(ΦωΦ)＜「演習」パート：既出問題の解説と実装