CF 611 D - New Year and Ancient Prophecy
年末に言ってたGoodBye2015の出来なかったやつ。
問題
長い数字の列を区切って数列としてみた時に、その数列が単調増加になっている(例見れば分かる)組合せの数。
問題概要
Limakは昔の予言が記された秘密の巻物を見つけた。秘密の巻物は桁の数字で構成される。最上位の桁が0であることはない。Limakは昔の言葉がわからないが、これはなんらかの特別な年のリストであると考えた。でも、コンマやスペースが見当たらないからどの年がリストされているのかよくわからない。以下のことを想定して桁の数字を区切っていく方法は何通りあるか:
- 年は単調増加( , つまり同じ年が連続するようなのはダメ)
- 全ての年は正の数
- 区切った時にリストのある要素に対して先頭に0がくるような区切り方はダメ
答えをで割った余りを出力せよ。
アイデア
Editorialを読みながら。
を巻物に書かれた文字の桁目で構成される数字として考える。また、巻物に書かれた数をで表し、文字目をで表す。
を「数字を分けた時に最後の数字がであるものの個数と定義する。すると、答えはで表される。このDPを計算したい。のサイズ的にまたはで出来るようにしたい。
まず、前提としてなら、である。最上位の桁が0であることは許されない。
さて、 に対して、がよりも小さくなるようなに対してを足しあげたい。この2つの数に対して、まず桁数が違うのなら桁が多い方が大きい数になるに決まっている。つまり、に対して注目すべき範囲は全部というわけではない。の桁数がなので、桁数に対して考慮するとを満たすは桁数が小さいのでまず全て足し上げて良い。すると、が欲しい。累積和を持っておけば速く計算できそう。
次に考慮すべきは、との桁数が一致する場合である。桁数に対して考慮するとを満たすただ1つのに対してのみ考慮すれば良いのは明らか。がの大小比較をする方法って何かあるだろうか。そもそもなので、巻物の数字はstring型で読み込むしか無い、そのstring型で保存した部分列の数字の大小をどうやって比較するのがいいんだろうか。ぱっと思いつけるのは最上位の桁から順に見ていって数字が違う桁が見つかった時点で大きい方が大きい数字であると断定できるが、これだと時間かかりそう...
Editorialでは2種類方法が紹介されている。まず1つ目は、ハッシュを使う方法で、固定したに対してとのどこが最初の異なる桁になるのかを二分探索で求めることが出来るらしいけど、ちょっと今は説明を見てもよくわからないので省略する。別の方法として、前述のに対してDPを使って求める方法がある。のときを満たす最小のを保存するという方法である。このDPのとき、に対してはかのどちらかになる。(とが一致するか否かで場合分けすれば良い)
求めたい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; }