TopCoder SRM 850 : Div1 Easy Div2 Hard EnclosedArea

ここまで参加者の少ないSRMは初めてでは…？
https://community.topcoder.com/stat?c=problem_statement&pm=17994

問題

整数E,Nが与えられる。
7セグメントで表現される正整数のうち、囲まれた領域がE個あるようなもののN番目のものを答えよ。

解法

典型的な桁DP。
以下を前処理で計算しておく。
f(d,e) := Leading Zeroを含めたd桁の整数で、囲まれた領域がe箇所あるようなものの数
g(d,e) := Leading Zeroを含めず、d桁以下の整数で、囲まれた領域がe箇所あるようなものの数

上記f,gがあれば、上の桁から順に0～9のどの値を取るかを決めていける。

int DB[10]={1,0,0,0,0,0,1,0,2,1};

ll p10[23];
ll dp1[23][23];
ll dp2[23][23];

class EnclosedArea {
	public:
	long long construct(int E, int N) {
		int i,d,x;
		
		ZERO(dp1);
		ZERO(dp2);
		p10[0]=1;
		dp1[0][0]=dp2[0][0]=1;
		for(i=0;i<=15;i++) {
			p10[i+1]=p10[i]*10;
			FOR(d,10) {
				FOR(x,21) {
					dp1[x+DB[d]][i+1]+=dp1[x][i];
					if(d) {
						dp2[x+DB[d]][i+1]+=dp1[x][i];
					}
					else {
						dp2[x][i+1]+=dp2[x][i];
					}
				}
			}
		}
		if(E==0) N++;
		
		ll cur=0;
		N++;
		for(d=15;d>=0;d--) {
			FOR(x,10) {
				if(cur||x) {
					if(DB[x]<=E) {
						if(N<=dp1[E-DB[x]][d]) {
							cur+=x*p10[d];
							E-=DB[x];
							break;
						}
						else {
							N-=dp1[E-DB[x]][d];
						}
					}
				}
				else {
					if(N<=dp2[E][d]) break;
					N-=dp2[E][d];
				}
			}
		}
		return cur;
		
	}
}

まとめ

Codeforcesなら、複数テストケースになってそうな問題。