SRM 403 DIV1 Hard TheLuckySum

SRM DP 数値の桁ごと 辞書順最小 ちょっとしたうまいやり方

問題 Editorial

問題

lucky numberとは、それを10進数で表記したときに4と7しか現れない正整数である。
整数nが与えられる。nを複数のlucky numberの総和で表す。lucky numberの数を最小化したい。そのような解のうち、辞書順最小のlucky numberの列を求めよ。ただしnがlucky numberの総和として表せないときは空配列を返せ。

  • 1 ≦ n ≦ 10^9

解答

lucky numberの数を全探索して、下から各lucky numberごとにやってsumを保持するような桁DP。lucky numberの数はまず全探索して、数が確定したら適当に辞書順greedyに、ある桁のk番目のdigitを固定するようにして毎回やる。
ここで1つ問題がある。それはleading zeroの問題。各lucky numberの桁数は異なることがある。そのため、終わったlucky numberは適切に"終わった"状態を持って常に0を足すようにしなければならないが、その"終わった"状態を単純に持とうとすると2^(lucky numberの数)かかってしまう(実際にはこれでも間に合うかも)。
ここである考えを自分は思いついた。
lucky numberの順序は任意で順序が変わっても総和は変わらなく、辞書順最小を求めたいので、ソートされているものだけを考えても答えは同じになる。
ソートされている場合、"終わった"状態は常に左から右へmonotone。つまり、「あるしきい値が存在して、それより左は終わっていて、それより右は終わっていない」ようになっている。そのため、状態としてそのしきい値のみを持てば十分。これによって状態数を少なくできる。
ところで、解のうちlucky numberの最大の個数はいくらだろうか？フォーラム参照。とりあえず、最大の数を9として問題ないらしい。
Editorial解では終わっていない数を持って、この桁での4の数と7の数を全探索してやっている。

コメント

順番関係ないのは重要。特にこの問題では「桁ごとに、自由に入れ替えても関係ない」というさらに強い性質も持っている。
自分の解法も終わっていない数を持っているのと同じことだ。自分の解法はそれをインクリメンタルにやっているように見える。しかし、この場合4と7で2値であるのでインクリメンタルにやらずとも計算量は同じになるようだ。

コード

#include <vector>
#include <cstring>
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define mset(m,v) memset(m,v,sizeof(m))
#define INF 0x3f3f3f3f
using namespace std;
typedef vector<int> vi;
const int MAXK = 10;
int ns[20];
char memo[12][10][10][MAXK+1][MAXK+1];
char heights[MAXK];
char fixd[MAXK][12];
struct TheLuckySum {
	int K;
	bool rec(int i, int d, int carry, int k, int endk) {
		char &r = memo[i][d][carry][k][endk];
		if(r != -1) return r;
		if(i == 11) r = d == 0;
		else if(k == K) r = d == ns[i] && rec(i+1, carry, 0, 0, endk);
		else {
			r = false;
			if(k < endk) {
				r = r || rec(i, d, carry, k + 1, endk);
			}else {
				if(heights[k] == -1 || i < heights[k]) {
					char f = fixd[k][i];
					if(f != 7) r = r || rec(i, (d + 4) % 10, carry + (d + 4) / 10, k + 1, endk);
					if(f != 4) r = r || rec(i, (d + 7) % 10, carry + (d + 7) / 10, k + 1, endk);
				}
				r = r || rec(i, d, carry, k + 1, k + 1);
			}
		}
		return r;
	}
	vector <int> sum(int n) {
		mset(ns, 0);
		{	int x = n, i = 0;
			while(x) ns[i ++] = x % 10, x /= 10;
		}
		int len = INF;
		mset(heights, -1);
		mset(fixd, -1);
		mset(memo, -1);
		for(K = 1; K <= MAXK; K ++) {
			mset(memo, -1);
			if(rec(0, 0, 0, 0, 0)) {
				len = K;
				break;
			}
		}
		if(len == INF) return vi();
		vi r(len);
		rep(i, len) {
			int height = 1;
			while(1) {
				mset(memo, -1);
				heights[i] = height;
				if(rec(0, 0, 0, 0, 0)) break;
				height ++;
			}
			for(int j = height-1; j >= 0; j --) {
				fixd[i][j] = 4;
				mset(memo, -1);
				if(!rec(0, 0, 0, 0, 0))
					fixd[i][j] = 7;
				r[i] = r[i] * 10 + fixd[i][j];
			}
		}
		return r;
	}
};