TopCoder SRM 665 Div1 Easy、Div2 Hard LuckySum

せっかくレート上がりそうだったのにunratedになり残念。
http://community.topcoder.com/stat?c=problem_statement&pm=13964

問題

10進数表記で、leading zeroを除き各桁4と7だけで構成された正整数をlucky numberと呼ぶ。
ここにあるN桁の整数が与えられる。ただし一部の桁は不明である。

この入力値の表記に合致する整数のうち、2つのlucky numberの和で表現できる最小値を求めよ。

解法

下の桁からDPで埋めていこう。
dp[桁][繰り上がり有無][未終了の数] = 入力に合致する下指定桁数の最小値
として状態を埋めていく。
未終了の数とは、leading zeroにまだなっていないlucky numberの数を示す。

各桁で取りうる値は以下のどれかである。

• 未終了の数が2なら、この桁で取りうる値は(繰り上がり+4+4)、(繰り上がり+4+7)、(繰り上がり+7+7)のどれか。
• 未終了の数が1以上なら、この桁で取りうる値は(繰り上がり+4)、(繰り上がり+7)のどれか。
• (繰り上がり)分のみ

上記６通りをためし、1の位が入力値表記に合致するするなら状態を更新していく。
なお、1の位だけは２つのlucky number共に0が取れないことに注意。

class LuckySum {
	public:
	long long construct(string note) {
		int i,x,y;
		ll p10[15];
		ll dp[16][2][3];
		
		p10[0]=1;
		FOR(i,14) p10[i+1]=p10[i]*10;
		FOR(i,16) FOR(x,2) FOR(y,3) dp[i][x][y]=1LL<<60;
		
		dp[0][0][2]=0;
		int L=note.size();
		int c,o;
		
		FOR(i,L) {
			char tar=note[L-1-i];
			
			FOR(c,2) FOR(o,3) if(dp[i][c][o]<1LL<<60) {
				ll v=dp[i][c][o];
				if(o>=2) {
					if(tar=='?' || tar==c+4+4+'0')      dp[i+1][0][2]=min(dp[i+1][0][2],v+8*p10[i]);
					if(tar=='?' || tar==(c+4+7)%10+'0') dp[i+1][1][2]=min(dp[i+1][1][2],v+11*p10[i]);
					if(tar=='?' || tar==(c+7+7)%10+'0') dp[i+1][1][2]=min(dp[i+1][1][2],v+14*p10[i]);
				}
				if(i) {
					if(o>=1) {
						if(tar=='?' || tar==c+4+'0') dp[i+1][0][1]=min(dp[i+1][0][1],v+4*p10[i]);
						if(tar=='?' || tar==c+7+'0') dp[i+1][0][1]=min(dp[i+1][0][1],v+7*p10[i]);
					}
					if(i==L-1 && c!=0) if(tar=='?' || tar==c+'0') dp[i+1][0][0]=min(dp[i+1][0][0],v);
				}
			}
		}
		ll ret=min(dp[L][0][0],min(dp[L][0][1],dp[L][0][2]));
		if(ret>=1LL<<60) ret=-1;
		
		return ret;
	}
}

まとめ

こういう桁DPはCodeforcesっぽいね。