一見簡単で地味に面倒な問題。
本番の正答率は0%だったようだ。
http://community.topcoder.com/stat?c=problem_statement&pm=11572
問題
0~(10^18-1)からなる数列を、以下の基準でソートする。
- 各桁の数値の総和が小さい方が前に来る。
- 上記総和が等しい場合、その数値を文字列化して辞書順で小さい方が前に来る。
上記基準でソートした数列のN番目の要素を答えよ。
解法
ソート基準の1つ目はさほど難しくないが、2つ目が厄介。
文字列化した辞書順だとleading zeroが無視され、"11"<"2"のように数値の大きさ順ではなくなる。
まず、各桁数・各桁の総和を状態として、そのような状態を取りうる数をDPでdp[桁数][各桁の総和]として求めておく。
ここで、このDPは2種類行う。
1つめはleading zeroが発生しない、すなわちdp[0][0]=0、dp[0][1~9]=1のケース。
もう一つはleading zeroが発生しうる、dp2[0][0~9]=1のケース。
まず、前者のDP結果を用いて、桁数は置いておいてN番目の要素が桁総和いくつの数列の何番目にあるかを求める。
次に、その桁総和をSとして、その中における要素を特定するが、後者のDP結果を使って次のように上の桁から定めていく。
今の桁を上からi番目とすると、今の桁をjとするとそのような数はdp2[17-i][S-j]+dp2[16-i][S-j]+...+dp2[0][S-j]通りある。
この組み合わせがN番目に近づくように上の桁から定めていく。
場合によっては途中の桁で終了する場合もある。
ll numf[19][180]; ll num[19][180]; class FoxAndSorting { public: string keta(int ke,int le, ll idx) { int d,i; if(le==0) { string s=""; FOR(i,idx-1) s+='0'; return s; } if(ke==0) { string s=""; s+=le+'0'; return s; } FOR(d,10) { if(ke==17 && d==0) continue; ll tot=(le==d); FOR(i,ke) tot+=num[i][le-d]; if(idx<=tot) { string s=""; s+='0'+d; return s + keta(ke-1, le-d, idx); } idx-=tot; } return ""; } long long get(long long idx) { int x,y,d; if(idx==1) return 0; idx--; ZERO(num); ZERO(numf); FOR(d,9) numf[0][d+1]=1; FOR(d,10) num[0][d]=1; FOR(x,17) FOR(y,180) FOR(d,10) numf[x+1][y+d] += numf[x][y]; FOR(x,17) FOR(y,180) FOR(d,10) num[x+1][y+d] += num[x][y]; FOR(x,18) FOR(y,180) numf[18][y]+=numf[x][y]; FOR(d,180) { if(idx<=numf[18][d]) return atoll(keta(17,d,idx).c_str()); idx -=numf[18][d]; } return 0; } };
まとめ
辞書順縛りのためにだいぶ苦労した…。