TopCoder SRM 771 Div1 Easy - AllEven

寝て起きたら解けた。

A以上B以下の整数のうち、0 ~ 9の各数字の出現回数が偶数である整数はいくつあるか、を求める問題。たとえば121222, 77, 355232などがこの条件を満たす。制約は0 <= A, B <= 10^18 - 1。

DPで解くことはわかっているのでそっち方面で考察を進める。

最初はdp[x][a][b]...[j]のようなDPを定義することを考えた。a, b, ..., jというのは0 ~ 9のそれぞれの出現回数。しかしこれだと、1種類の数字の出現回数の最大は18回なので、18¹⁰程度のメモリ領域が必要になる。これだとMLEなのでもう少し考える必要がある。

ここで条件に注目する。出現回数が偶数ということは、出現回数を2で割った余りが0ということである。よって、出現回数そのものを保存する必要はなく、出現回数を2で割った余りを保存しておけばいい。これで状態数を18¹⁰から2¹⁰に減らせる。

更にいうと、ひとつの数字につき状態数が2ということはbitDPが使える。だからdp[x][a][b]...[j]のようにa ~ jを用意する必要はなく、dp[x][s]とsのひとつで状態を表せる（sは0 <= s < 2^18を満たす）。

大まかな流れとしては、dp[x][s]というDPを定義し、各桁で0 ~ 9の数字を選んだときに状態がdp[x + 1][s ^ (1 << d)]（dは選んだ数字）に移るとすればいい。

次に細部を詰めていく。

各桁で選ぶ数字を決めていくときに上限を超えてはいけない。たとえば上限が532のときに、3桁目で6を選んではならない。これを解決する方法として桁DPを使う。

もう一点考えることがあり、たとえば先ほどの例の3桁目で0を選んだとき、それは「何の数字も選んでいない」ことと同じであるため、sの状態を変化させてはならない。よって、「上位桁に1以上の数字があるか」の状態も持つ必要がある。この条件を満たさないとき、数字0を選んだときの遷移先はdp[x + 1][s]となる。

以上をまとめると、DPの定義は次のようになる。

dp[x][y][z][s] := 上からx桁目で、0 ~ 9の各出現回数の状態がsのときの数え上げ数。yは桁DP、zは「上位桁に1以上の数字があるか」を表す。

遷移については、上限の上からx桁目はいくつか、y、z、x番目に選ぶ数字は何かの4つにより遷移先が決まる。具体的にどのような遷移になるかについては長くなってしまうので割愛。

#include <bits/stdc++.h>

#define rep(i, n) for (int i = 0; i < int(n); i++)
#define repc(i, n) for (int i = 0; i <= int(n); i++)
#define bit(b) (1ll << (b))

using namespace std;

using i64 = long long;

template <typename T> inline T power(T x, i64 n, T e = 1) { T r = e; while (n > 0) { if (n & 1) r *= x; x *= x; n >>= 1; } return r; }

i64 dp[20][2][2][bit(10)];

i64 cont(i64 n) {
  rep(i, 20) rep(j, 2) rep(k, 2) rep(l, bit(10)) {
    dp[i][j][k][l] = 0;
  }
  dp[0][0][0][0] = 1;
  rep(i, 18) {
    int x = (n / power(10ll, 18 - i - 1)) % 10;
    rep(j, 2) rep(k, 2) rep(l, bit(10)) {
      if (j == 0) {
        repc(m, x) {
          if (m == x) {
            if (k || m) {
              dp[i + 1][0][1][l ^ (1 << m)] += dp[i][j][k][l];
            } else {
              dp[i + 1][0][0][l] += dp[i][j][k][l];
            }
          } else {
            if (k || m) {
              dp[i + 1][1][1][l ^ (1 << m)] += dp[i][j][k][l];
            } else {
              dp[i + 1][1][0][l] += dp[i][j][k][l];
            }
          }
        }
      } else {
        repc(m, 9) {
          if (k || m) {
            dp[i + 1][1][1][l ^ (1 << m)] += dp[i][j][k][l];
          } else {
            dp[i + 1][1][0][l] += dp[i][j][k][l];
          }
        }
      }
    }
  }
  return dp[18][0][1][0] + dp[18][1][1][0];
}

struct AllEven {
  i64 countInRange(i64 lo, i64 hi) {
    i64 l = cont(max(0ll, lo - 1));
    i64 h = cont(hi);
    return h - l;
  }
};

zの定義を「もう0以外の数字を選んだかどうか」としていたけど、kmjpさんの記事では「上の桁に1以上の値があるか」と表現されていた。こちらのほうが断然わかりやすいので、これからはこの表現を使っていく。

あと、DPの状態数が多い場合は「dp[i][j]... := XXX」と書くのではなく、以下のように書いたほうがわかりやすいかもしれない。

dp[x][y][z][s] は数え上げ数

x : 上から何桁目か
y : 桁DP
z : 上位桁に1以上の数字があるか
s : 0 ~ 9の出現回数を2で割った余り

こちらのフォーマットのほうが、状態数が増えたときに対応しやすい。

ぺんぎんメモ

プログラミングのメモです。たまに私生活のことや鬱っぽいことを書きます。

TopCoder SRM 771 Div1 Easy - AllEven