SRM 402 DIV1 Hard IncreasingSequence

SRM DP 文字列

問題 Editorial

問題

'0'〜'9'からなる文字列digitsが与えられる。
この文字列をいくつかに分割し、それぞれを整数として読む(leading zeroは許可され、単に無視される)。ただし、列はstrictly increasingでなければならない。
このような列の中で、最後の整数を最小化したい。そのような列の中で辞書順最大の列を求め、その列の総乗を求めよ。

  • 1 ≦ |digits| ≦ 2500

解答

Editorialを参考にした。
strictly increasingを考えるために、文字列上の2つの区間を整数として比較したい。
まず、次の非ゼロの位置をそれぞれの位置に対して求める(nextnonzeroposとする)。これは右からのDPで求められる。すると区間[a,b)と[c,d)の比較は[nextnonzeropos[a],b)と[nextnonzeropos[c],d)の(長さ, 辞書順)の比較となる。つまり、この処理の後の区間では、長さが違う場合は常に長さが大きいほうが大きい整数を表す。
同じ長さの場合、lcp(longest common prefix)の次の文字を比較することによってΘ(1)で辞書順比較ができる。lcpはΘ(n^2)のDPによって計算してもよいし、suffix arrayを使ってΘ(n)でheight arrayを構築してRMQで求めてもよい。
最後の整数が最小かつ辞書順最大というものを求めるのに、2回DPをする。
まず"dp1[i] = 区間[j,i)と分割することが可能な最大のj = if i == 0 then 0 else max{ 0≦j＜i | [dp1[j],j)＜[j,i)}"とする(ここで"＜"はdigitsの区間を数値として見た時の比較)。このとき[dp1[n],n)が最小の最後の数となる(n=|digits|)。これが正しいことは、(1. dp1[j]が大きいほど[dp1[j],j)は数として小さくなるので常に最大のjをとれば良い, 2. 同様にdp1[n]が大きいほど最後の整数が最小化される)というようにわかる。
次に"dp2[i] = 解のうち区間[i,j)と分割できる最大のj = if nextnonzeropos[i] == nextnonzeropos[dp1[n]] then n else max({⊥}∪{ i＜j≦n | dp2[j]≠⊥, [i,j)＜[j,dp2[j]) })"とする。iがdp1[n]またはそのleading zeroと同じ時は[i,n)を使えること、またそれより右側は必ず⊥となるので[dp1[n],n)が整数として保存されること、さらにleading zeroを自由に付加できる事に注意する。
最後にi=0からgreedy(これによって辞書順最大となる)に区間をたどっていけばよい。総乗は普通に剰余演算でやればよい。
EditorialによればDPの部分も線形時間でできるらしい。

コメント

最後のdp1[n]の整数(文字列でなく。leading zeroは自由にくっつけてよい)を保存しつつgreedyにやるやり方は少しトリッキーだ。

コード

#include <string>
#include <vector>
#include <cstring>
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define each(it,o) for(__typeof((o).begin()) it = (o).begin(); it != (o).end(); ++ it)
#define mset(m,v) memset(m,v,sizeof(m))
#define INF 0x3f3f3f3f
using namespace std;

template<unsigned MOD>
struct ModInt {
	unsigned x;
	ModInt(): x(0) { }
	ModInt(signed sig) { if((x = sig % MOD + MOD) >= MOD) x -= MOD; }
	unsigned get() const { return x; }

	ModInt &operator+=(ModInt that) { if((x += that.x) >= MOD) x -= MOD; return *this; }
	ModInt &operator*=(ModInt that) { x = (unsigned long long)x * that.x % MOD; return *this; }

	ModInt operator+(ModInt that) const { return ModInt(*this) += that; }
	ModInt operator*(ModInt that) const { return ModInt(*this) *= that; }
};

typedef ModInt<1000000003> mint;
int nextnonzeropos[2501];
short lcp[2501][2501];
struct IncreasingSequence {
	string digits;
	bool rankle(int i, int j, int k, int l) {
		i = nextnonzeropos[i];
		k = nextnonzeropos[k];
		if(i >= j && k >= l) return true;
		if(i >= j) return true;
		if(k >= l) return false;
		if(j - i != l - k) return j - i < l - k;
		int p = lcp[i][k];
		if(p >= j - i) return true;
		return digits[i+p] <= digits[k+p];
	}
	mint getnumber(int i, int j) {
		mint r = 0;
		while(i < j) {
			r = r * 10 + mint(digits[i] - '0');
			i ++;
		}
		return r;
	}
	bool ranklt(int i, int j, int k, int l) {
		return !rankle(k, l, i, j);
	}
	int getProduct(vector <string> digits_) {
		each(i, digits_) digits += *i;
		int n = digits.size();
		nextnonzeropos[n] = INF;
		for(int i = n-1; i >= 0; i --) {
			if(digits[i] == '0')
				nextnonzeropos[i] = nextnonzeropos[i+1];
			else nextnonzeropos[i] = i;
		}
		rer(i, 0, n) lcp[n][i] = lcp[i][n] = 0;
		for(int i = n-1; i >= 0; i --)
			for(int j = n-1; j >= 0; j --)
				lcp[i][j] = digits[i] == digits[j] ? lcp[i+1][j+1]+1 : 0;
		static int f[2501];
		f[0] = 0;
		rer(j, 1, n) {
			for(int i = j-1; i >= 0; i --)
				if(ranklt(f[i], i, i, j)) {
					f[j] = i;
					break;
				}
		}
		int lasti = f[n];
		static int g[2501];
		mset(g, -1);
		for(int i = n-1; i >= 0; i --) {
			//ここでnextnonzeroposを使っているところに注意！
			if(nextnonzeropos[i] == nextnonzeropos[lasti]) g[i] = n;
			else for(int j = n; j > i; j --)
				if(g[j] >= 0 && ranklt(i,j,j,g[j])) {
					g[i] = j;
					break;
				}
		}
		mint r = 1;
		for(int i = 0; i < n; i = g[i])
			r *= getnumber(i, g[i]);
		return r.get();
	}
};