Shiraz University Local Contest 2011 A, UVa-12377 : Number Coding

問題概要

長さL(<20)の数字からなる文字列が与えられる。これらをN個に分割する。分割したとき非減少になっていなくてはならない。これらの数字を9個に割り振る方法が何通りあるか求める問題。

考えたこと

桁数と直前の値を状態としてDP?
いやいや、値が小さいんだから全探索で行ける。comb(20, 9)も大した大きさではないし間に合うはず。
分割を全部試した後は単純な組み合わせの問題に落ちるはず。
最初はTLEしてもいいからmap使って正確に書こう。
サンプル通った。WA。
オーバーフローのことを真面目に考えていなかった。19文字の数字とか出てくるんだし64ビットじゃなきゃダメだろう。
まだWA。もしかしてN=0の場合があるのか？
さらにWA。もう直すところが思いつかなかったので自棄になってleading zeroのチェックを外したら通った。

本番で通ったコード

計算量O(2^L*L)にlogが付く位？

#include <cstdio>
#include <cstring>
#include <map>
using namespace std;

typedef long long int64;

const int MAX_L = 20;
int N, L;
char str[MAX_L+2];
int64 comb[MAX_L+1][MAX_L+1];
int64 fact[MAX_L+1];

int64 get_comb(const map<int,int>& dict){

	int64 ans = comb[9][N] * fact[N];
	for(map<int,int>::const_iterator itr=dict.begin(); itr!=dict.end(); itr++){
		ans /= fact[itr->second];
	}

	return ans;
}

int64 get_num(int from, int to){
	int64 ret = 0;
	if(0 && str[from] == '0'){
		return -1;
	}
	for(int i=from; i<to; i++){
		ret = 10 * ret + (str[i] & 15);
	}

	return ret;
}

int64 try_it(const int bit){
	if( !((bit>>(L-1))&1) ){
		return 0;
	}
	map<int, int> dict;

	int prev_vert = 0;
	int64 prev_val = 0;
	for(int i=0; i<L; i++)if((bit>>i)&1){
		int64 cur_val = get_num(prev_vert, i+1);
		if(cur_val < prev_val){
			return 0;
		}
		dict[cur_val]++;
		prev_vert = i+1;
		prev_val = cur_val;
	}


	return get_comb(dict);
}

int64 solve(){
	L = strlen(str);
	N = str[0] & 15;
	if(N==0){
		return 1;
	}
	if(N==1){
		return 9;
	}
	for(int i=0; i<L; i++){
		str[i] = str[i+1];
	}
	L--;

	int64 ans = 0;
	for(int bit=0; bit<(1<<L); bit++)if(__builtin_popcount(bit) == N){
		ans += try_it(bit);
	}

	return ans;
}

int main(){

	fact[0] = 1;
	for(int i=0; i<10; i++){
		fact[i+1] = (i+1)*fact[i];
	}

	for(int i=0; i<=MAX_L; i++){
		comb[i][0] = comb[i][i] = 1;
		for(int j=1; j<i; j++){
			comb[i][j] = comb[i-1][j] + comb[i-1][j-1];
		}
	}

	int T;
	scanf("%d ", &T);
	while(T--){
		scanf("%[^\n]%*c", str);
		printf("%lld\n", solve());
	}

	return 0;
}