SRM 592 Div II

http://community.topcoder.com/stat?c=round_overview&er=5&rd=10664

練習。

	Problem	Status	Points
250	LittleElephantAndBooks	Passed System Test	215.14
500	LittleElephantAndPermutationDiv2	Passed System Test	475.77
1000	LittleElephantAndArray	Failed System Test	0.00

250に12分
500に6分
1000に数日

苦手としている数え上げとDPを強化するために1000に時間を費やした。今回のエントリでは、1000のみを記載することにする。

LittleElephantAndArray

http://community.topcoder.com/stat?c=problem_statement&pm=12704&rd=15704

苦手な数え上げとDPを強化するために、数日かけて考察を行った。

以下のようなアプローチを取ることにした
- 計算量、メモリ使用量を考え、見積もる
- 大きな値で落としてしまってもよいので、まずメモ化再帰で実装する
- 再度考察を行い、DPに書き換える
- 必要ならば、さらに計算量とメモリ使用量を落とす

まずサンプルを理解するのに時間がかかった

A = 10、N = 2の場合は、以下の数列となる。

10 11 12

それぞれの数値は任意の桁を選ぶことによって変えることができる。例えば10であれば、0、1、10に変えられる
全ての組み合わせの中で、以下の条件を満たす数列がいくつ出来るか答える問題

(0, 1, 1)はこの条件を満たすが、(0, 11, 2)は満たさない

計算量とメモリ使用量を考察する
- いきなりDPでの解法を考えず、メモ化再帰で解くとしたらどうするかを考えてみる

制約は以下だ

例えば、「i番目の数値がj以上の場合について考える」メモ化再帰は計算量、メモリ使用量ともに現実的ではない
メモリ使用量はO(NM)だ

Nは最大で大体10¹⁵となる
- 必要とするメモリ使用量は大変大きいものとなる

さて、Nの最大値は大変大きいが、その組み合わせ数はそれほど大きくない
- 数値の最大の桁数が16桁であるので、高々2¹⁶
- 全ての桁を選ばない選択肢はないので、正確には2¹⁶ - 1ではある
これを使うと、「i番目の数値のj番目の組み合わせの数について考える」メモ化再帰のメモリ使用量は現実的なものとなる

1,000,000,007の剰余を取ることを考えるとメモ化再帰で記録するのはint型の整数でよい
実際のメモリ使用量は以下となる。TopCoderで使えるメモリが64MBであることを考えても十分収まる

ではメモ化再帰の実装の詳細を考察してみよう
- (A, N) = (10, 2)を用いる(10、11、12の数列となる入力)

数え上げを木構造で表してみよう
- まずは全探索を視覚化する

便宜上仮想的な根の頂点も図示しておく

ここで全探索の計算量を考えてみよう
- 数値一つにつき最大2¹⁶組み合わせを試せばよい

つまり、計算量は以下となる

これを計算する。想像を絶するような大きな値となってしまうことが分かる(ざっくりと480桁ほど)

さて、問題の条件を満たす数列とはどのようなものであっただろうか
- 以下は再掲である

値が11の頂点から12の頂点には進めるが、11の頂点から2の頂点には進めない
- そのような経路は条件的に成立しないため、数えなくてよいのだ
- 図に反映してみよう

この図で最後まで成立している経路を数えてみよう
- そのような経路は15個あることが分かる。そのため15通りの組み合わせがあると考えてよい

さて、成立しない経路はどうせ数えないので、描画するのもやめてしまおう

随分すっきりした木構造となってきた

同じ要素からなる部分木がいくつも散見される。これらは無駄な計算を行っているし、省略できる

同じ計算を行ってしまう部分木を図示してみよう

同じ計算をするのであれば、再利用するように辺を張り替えてみよう

考慮すべき頂点の数が随分と減ったことが分かる
また、末端の頂点に関しても無駄な計算を行っている

これらに関しても計算結果を再利用できるように工夫してみよう

これが最適な結果だ
- ...と言われても、この図は「最適」という言葉にふさわしいものではない。むしろ醜い
- 頂点の水平方向の位置が問題なのだ
- 頂点と辺の関係を変えずに、頂点の水平方向の位置をずらしてみよう

先ほどと同じ意味の図とは思えないほど理路整然とした
- メモ化再帰のメモリ構造の形も一気に見えてきた

さて、メモリ使用量を考察しよう
- メモリ使用量はO(NM)である

Nは高々2¹⁶であるので、メモリ使用量は余裕があることが分かる

さてここで、計算量を考察しよう
- 頂点は複数の頂点にその計算結果を「配っている」
  - 見方を変えると、頂点は複数の頂点から計算結果を「集めている」とも言える
- そのため、計算量はO(N²M)となってしまう

Nが高々2¹⁶であっても、計算量は大き過ぎることが分かった

このアルゴリズムだと大きなAに対して解けないことが分かったが、メモ化再帰として実装してみよう

以下の実装はシステムテストを通らない。

#define MOD 1000000007


std::string lltos(long long ll)
{
  std::ostringstream oss;

  oss << ll;

  return oss.str();
}


class LittleElephantAndArray {
public:
  int getNumber(long long A, int N) {
    N_ = N;
    
    numbers_.assign(N_ + 1, std::vector<long long>());
    
    for (int i = 0; i <= N_; i ++) {
      std::string s(lltos(A + i));
      
      for (int j = 1, size = s.size(); j < (1 << size); j ++) {
        long long n = 0;

        for (int k = 0; k < size; k ++)
          if (j & (1 << k)) {
            n *= 10;
            n += s[k] - '0';
          }

        numbers_[i].push_back(n);
      }
      
      std::sort(ALL(numbers_[i]));
    }
    
    memo_.clear();
    
    long long c = 0;
    
    for (int i = 0, size = numbers_[0].size(); i < size; i ++)
      c = (c + dfs(0, i)) % MOD;
    
    return c;
  };
  
  long long dfs(int i, int j) {
    if (i == N_)
      return 1;

    std::pair<int, int> key(i, j);
    
    if (memo_.count(key))
      return memo_[key];

    long long c = 0;

    for (int k = 0, size = numbers_[i+1].size(); k < size; k ++)
      if (numbers_[i+1][k] >= numbers_[i][j])
        c = (c + dfs(i + 1, k)) % MOD;

    return memo_[key] = c;
  };

private:
  int N_;

  std::vector<std::vector<long long>> numbers_;
  
  std::map<std::pair<int, int>, long long> memo_;
};

さて、一先ず小さなケースに対しての実装はできた
- 考え方は大きくずれてはいないだろう

それぞれの数値から得た数値群は整列して格納した
long longなのでメモリをかなり消費するが、今はいいとしておく

方向性の信憑性が増したところで、DPに書き換えてみよう

まず図に数値を書き込んでみる

最上段の頂点群を選ぶ組み合わせ数はそれぞれ1
再下段の頂点群に集まって来た値を合計したものが求める組み合わせ数だ

グラフが様々な形をしていると戸惑うことがあるが、動的計画法の例でよく提示されている以下のような問題の考え方と全く変わらない

有効な頂点に「流れ込んでくる」組み合わせ数を合計してやればよい

これを全ての頂点に対して処理する

形は異なれど、この問題に対してもこれと同じことをしてやればよい

さて、DPには「配るDP」と「集めるDP」があるようだが、ここでは「集めるDP」を基調としてDPを実装してみる
- 計算量に関してはメモ化再帰と比べて何ら改善されていない。O(N²M)のままだが、それでよいとする

以下の実装はシステムテストを通らない。

int dp[111][66666];

class LittleElephantAndArray {
public:
  int getNumber(long long A, int N) {
    std::vector<std::vector<long long>> numbers(N + 1);
    
    for (int i = 0; i <= N; i ++) {
      std::string s(lltos(A + i));

      for (int j = 1, size = s.size(); j < (1 << size); j ++) {
        long long n = 0;

        for (int k = 0; k < size; k ++)
          if (j & (1 << k)) {
            n *= 10;
            n += s[k] - '0';
          }

        numbers[i].push_back(n);
      }
      
      std::sort(ALL(numbers[i]));
    }

    memset(dp, 0, sizeof(dp));

    for (int j = 0, size1 = numbers[0].size(); j < size1; j ++)
      dp[0][j] = 1;
      
    for (int i = 1; i <= N; i ++)
      for (int j = 0, size1 = numbers[i].size(); j < size1; j ++)
        for (int k = 0, size2 = numbers[i-1].size(); k < size2; k ++)
          if (numbers[i-1][k] <= numbers[i][j])
            dp[i][j] = (dp[i][j] + dp[i-1][k]) % MOD;

    long long c = 0;

    for (int j = 0, size = numbers[N].size(); j < size; j ++)
      c = (c + dp[N][j]) % MOD;

    return c;
  };
};

脱線するが、以下は「集めるDP」を図示したもの

「配るDP」を図示したものと比較すると面白い

さて、ここからは計算量を落とすことを考えよう
よく観察すると、(0, 1, 2)と(1, 1, 2)等の経路は(?, 1, 2)として考えることができる
- つまり、数値が1の頂点には、1以下の頂点のものの組み合わせの数の合計を流し込んでしまえばよい
合計を加味した辺の構成を考えてみよう

また、頂点の数値以下の最大の値の頂点を接続する辺は以下のようなものとなる

この二つの考え方を合成してみる

これで準備は完了だ
- 辺がすっきりした

数値を書き込んでみよう

「i番目の数値の組み合わせのj番目に流れ込んで来た組み合わせ数の合計」が求める組み合わせ数である

さて、数値がnの頂点に接続することが出来る頂点を探すにはどうしたらよいだろうか?
- 整列もしているし、二分探索をするのが最適だ
- この問題の場合、std::upper_boundを用いるのがよさそうだ

計算量は以下のように落ちる

数値的にも面白いくらいに落ちる

これを実装する

以下の実装はシステムテストを通らない。

int dp[111][66666];

class LittleElephantAndArray {
public:
  int getNumber(long long A, int N) {
    std::cerr << A << ' ' << N << ':' << std::endl;

    std::vector<std::vector<long long>> numbers(N + 1);
    
    for (int i = 0; i <= N; i ++) {
      std::string s(lltos(A + i));

      for (int j = 1, size = s.size(); j < (1 << size); j ++) {
        long long n = 0;

        for (int k = 0; k < size; k ++)
          if (j & (1 << k)) {
            n *= 10;
            n += s[k] - '0';
          }

        numbers[i].push_back(n);
      }
      
      std::sort(ALL(numbers[i]));
    }

    for (int j = 0, size = numbers[0].size(); j < size; j ++)
      dp[0][j] = j + 1;

    for (int i = 1; i <= N; i ++)
      for (int j = 0, size = numbers[i].size(); j < size; j ++) {
        dp[i][j] = j ? dp[i][j-1] : 0;

        int k = std::upper_bound(ALL(numbers[i-1]), numbers[i][j]) - numbers[i-1].begin();
      
        if (k)
          dp[i][j] = (dp[i][j] + dp[i-1][k-1]) % MOD;
      }

    return dp[N][numbers[N].size()-1];
  };
};

さて、これでもまだシステムテストを通らない
- 大きなAとNに対しては、使用しているメモリ使用量が64MBを超えることがある

数値を組み合わせた数はlong longで保持しているので8バイト、DPの値はintで保持しているので4バイトである

数値の組み合わせ数を全て保持しているのが問題であるようだ
- DPのメモリ使用量については問題なさそうだ

では数値の組み合わせをDPの処理が進むにつれ生成するように変更しよう

以下の実装はシステムテストを通る。

int dp[111][66666];


class LittleElephantAndArray {
public:
  int getNumber(long long A, int N) {
    std::vector<std::string> ss;

    for (int i = 0; i <= N; i ++)
      ss.push_back(lltos(A + i));

    std::vector<long long> curr, prev;

    fill_numbers(ss[0], prev);

    for (int j = 0, size = prev.size(); j < size; j ++)
      dp[0][j] = j + 1;

    for (int i = 1; i <= N; i ++) {
      fill_numbers(ss[i], curr);
      
      for (int j = 0, size = curr.size(); j < size; j ++) {
        dp[i][j] = j ? dp[i][j-1] : 0;

        int k = std::upper_bound(ALL(prev), curr[j]) - prev.begin();
      
        if (k)
          dp[i][j] = (dp[i][j] + dp[i-1][k-1]) % MOD;
      }

      curr.swap(prev);
    }

    return dp[N][prev.size()-1];
  };

private:
  void fill_numbers(const std::string& s, std::vector<long long>& numbers) const {
    numbers.clear();

    for (int i = 1, size = s.size(); i < (1 << size); i ++) {
      long long n = 0;

      for (int j = 0; j < size; j ++)
        if (i & (1 << j)) {
          n *= 10;
          n += s[j] - '0';
        }
      
      numbers.push_back(n);
    }
      
    std::sort(ALL(numbers));
  };
};