せっかくレート上がりそうだったのに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)のどれか。
- (繰り上がり)分のみ
上記6通りをためし、1の位が入力値表記に合致するするなら状態を更新していく。
なお、1の位だけは2つの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っぽいね。