kmjp's blog

競技プログラミング参加記です

TopCoder SRM 535 Div2 Hard FoxAndSorting

一見簡単で地味に面倒な問題。
本番の正答率は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;
	}

};

まとめ

辞書順縛りのためにだいぶ苦労した…。