裏紙

ほぼ競プロ、たまに日記

CF 611 D - New Year and Ancient Prophecy

年末に言ってたGoodBye2015の出来なかったやつ。

問題

Problem - 611D - Codeforces

長い数字の列を区切って数列としてみた時に、その数列が単調増加になっている(例見れば分かる)組合せの数。

問題概要

Limakは昔の予言が記された秘密の巻物を見つけた。秘密の巻物は n桁の数字で構成される。最上位の桁が0であることはない。Limakは昔の言葉がわからないが、これはなんらかの特別な年のリストであると考えた。でも、コンマやスペースが見当たらないからどの年がリストされているのかよくわからない。以下のことを想定して n桁の数字を区切っていく方法は何通りあるか:

  • 年は単調増加({y_1 \lt y_2 \lt ... \lt y_n} , つまり同じ年が連続するようなのはダメ)
  • 全ての年は正の数
  • 区切った時にリストのある要素に対して先頭に0がくるような区切り方はダメ

答えを{10^9 + 7}で割った余りを出力せよ。

イデア

Editorialを読みながら。

 \{ x ... y \} を巻物に書かれた文字の x, x+1, ... , y桁目で構成される数字として考える。また、巻物に書かれた数を sで表し、 x文字目を s[x]で表す。

 dp[b][c]を「数字を分けた時に最後の数字が \{b ... c\}であるものの個数と定義する。すると、答えは\displaystyle \sum_{i=1}^{n} dp[i][n]で表される。このDPを計算したい。 nのサイズ的に O(n^2)または O(n^2logn)で出来るようにしたい。

まず、前提として s[i]=0なら、 dp[i][c]=0である。最上位の桁が0であることは許されない。

さて、  dp[b][c]に対して、 \{ a ... b-1 \}  \{ b ... c \} よりも小さくなるような aに対して dp[a][b-1]を足しあげたい。この2つの数に対して、まず桁数が違うのなら桁が多い方が大きい数になるに決まっている。つまり、 aに対して注目すべき範囲は全部というわけではない。 \{ b ... c \} の桁数が c-b+1なので、桁数に対して考慮すると (b-1)-a \lt c-bを満たす aは桁数が小さいのでまず全て足し上げて良い。すると、\displaystyle \sum_{a=2b-c}^{b-1} dp[a][b-1]が欲しい。累積和を持っておけば速く計算できそう。

次に考慮すべきは、 \{ a ... b-1 \}  \{ b ... c \} の桁数が一致する場合である。桁数に対して考慮すると (b-1)-a = c-bを満たすただ1つの aに対してのみ考慮すれば良いのは明らか。 \{ a ... b-1 \}  \{ b ... c \} の大小比較をする方法って何かあるだろうか。そもそも n \le 5000なので、巻物の数字はstring型で読み込むしか無い、そのstring型で保存した部分列の数字の大小をどうやって比較するのがいいんだろうか。ぱっと思いつけるのは最上位の桁から順に見ていって数字が違う桁が見つかった時点で大きい方が大きい数字であると断定できるが、これだと時間かかりそう...

Editorialでは2種類方法が紹介されている。まず1つ目は、ハッシュを使う方法で、固定した a,bに対して \{a...\} \{b...\}のどこが最初の異なる桁になるのかを二分探索で求めることが出来るらしいけど、ちょっと今は説明を見てもよくわからないので省略する。別の方法として、前述の a,bに対してDPを使って求める方法がある。 nxt[a][b]=xのとき s[a+x] \neq s[b+x]を満たす最小の xを保存するという方法である。このDPのとき、 nxt[a][b]に対しては nxt[a][b] = nxt[a+1][b+1]+1 nxt[a][b] = 0のどちらかになる。( s[a] s[b]が一致するか否かで場合分けすれば良い)

求めたいDPを時間内に計算するために別のDPをする発想なんて頭の中にはなかった...しかもそもそも区間DP初めてかも

実装(C++)

#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <algorithm>
#include <set>
#include <sstream>
#include <utility>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cctype>
#include <climits>
using namespace std;

typedef long long ll;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) for(int i=0;i<(n);++i)
#define foreach(itr,c) for(__typeof(c.begin()) itr=c.begin(); itr!=c.end(); itr++)

const long mod=(long)1e9+7;

int n;
string str;

int s[5001];

long dp[5005][5005]={0};
long dpsum[5005][5005]={0}; //sum of dp[1..a][b]

int nxt[5005][5005]={0};


int main(int argc, char const *argv[]) {
  cin >>n >>str;

  for(int i=1; i<=n; ++i) s[i]=str[i-1]-'0';

  //まずnxtを埋めておく
  for(int a=n-1; a>=1; --a){
    for(int b=n-1; b>0; --b){
      nxt[a][b]=((s[a]!=s[b]) ? 0 : (nxt[a+1][b+1]+1) );
      //printf("nxt[%d][%d]= %d\n",a,b,nxt[a][b]);
    }
  }

  for(int c=1; c<=n; ++c){
    dp[1][c]=1;

    for(int b=1; b<=c; ++b){
      if(s[b]!=0){
        int a=2*b-c;
        if(a<1) a=1;

        dp[b][c] += dpsum[b-1][b-1]-dpsum[a-1][b-1];
        if(dp[b][c]<0) dp[b][c]+=mod;

        a=2*b-c-1;
        if(a>=1){
          int d=nxt[a][b];
          if(d<=c-b && s[a+d]<s[b+d])
            dp[b][c]=(dp[b][c]+dp[a][b-1])%mod;
        }

        //printf("dp[%d][%d] = %d\n", b,c,dp[b][c]);
      }

      dpsum[b][c]=(dpsum[b-1][c]+dp[b][c])%mod;
    }
    
  }

  std::cout << dpsum[n][n] << std::endl;

  return 0;
}