TopCoder SRM 752 Div1 Easy Div2 Hard ReconstructNumber

SRMでは珍しいタイプ？
https://community.topcoder.com/stat?c=problem_statement&pm=15312

問題

N桁の正整数値がある。
この値は直接的には与えられないが、隣接する数字同士が以下のいずれの関係にあるかが与えられる。

• 等しい
• 等しくない
• 上の桁の方が小さい
• 下の桁の方が小さい

条件を満たす値のうちLeading Zeroを含まない最小値を求めよ。

解法

以下を後ろの位から貪欲に埋めていく。
f(n,k) := 上からn桁目がkの場合、以後条件を満たすことが可能か。また可能なら(n+1)桁目の最小値を格納する。

f(n,k)がわかっているなら、(n-1)桁目の値a、(n)桁目の値bを総当たりし、a,bが条件を見たし、かつf(n,b)が条件を満たすようなbのうち最小値をf(n-1,a)とすればよい。

int nex[2020][10];

class ReconstructNumber {
	public:
	string smallest(string C) {
		MINUS(nex);
		int N=C.size();
		
		if(N==0) return "1";
		int i,j,k;
		FOR(i,10) nex[N][i]=1;
		for(i=N-1;i>=0;i--) {
			FOR(j,10) FOR(k,10) if(nex[i+1][k]>=0) {
				if(C[i]=='=' && j!=k) continue;
				if(C[i]=='!' && j==k) continue;
				if(C[i]=='<' && j>=k) continue;
				if(C[i]=='>' && j<=k) continue;
				nex[i][j]=k;
				break;
			}
		}
		
		string S;
		for(int cur=1;cur<=9;cur++) if(nex[0][cur]>=0) {
			S.push_back('0'+cur);
			FOR(j,N) {
				cur=nex[j][cur];
				S.push_back('0'+cur);
			}
			return S;
		}
		return "";
		
		
	}
}

まとめ

こういうのSRM Easyで出るイメージないなぁ。