kmjp's blog

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

ABBYY Cup 3.0 : A. Special Task

ABBYY Cupは不参加なので復習だけ。
http://codeforces.com/contest/316/problem/A2

問題

途中の桁に"?"またはA~Jの文字を含んだ数字のヒント情報が与えられる。
?はどんな数字を入れてもよく、同じアルファベットは同じ数字、異なるアルファベットは異なる数字を入れなければならない。
先頭が0でないようにする場合、ヒント情報に合致する数字の数を答えよ。

問題

先頭以外の"?"は何を入れてもいいので、1つ?が出るたびに答えは10倍する。
先頭の"?"は1~9を入れればよいので、答えは9倍する。
A~Jのうちi個が登場するなら答えは{}_{10} P_i倍になる。
ただし、いずれかの文字が先頭に来るなら、そこは1~9を入れないといけないので9 \times {}_9 P_{i-1}倍とすればよい。

int L;
char str[100001];
int num[10];

void solve() {
	int f,r,i,j,k,l, x,y;
	int q=0;
	
	GETs(str);
	L=strlen(str);
	FOR(i,L) {
		if(str[i]=='?') q++;
		if(str[i]>='A' && str[i]<='J') num[str[i]-'A']++;
	}
	
	ll res=1;
	if(str[0]=='?') {
		res *= 9;
		q--;
	}
	
	j=10;
	if(str[0]>='A' && str[0]<='J') FOR(i,10) if(num[i]) res *= min(9,j--);
	else FOR(i,10) if(num[i]) res *= j--;
	
	_P("%lld",res);
	while(q--) _P("0");
	_P("\n");

	return;
}

まとめ

1問目なのでまだ簡単。

広告を非表示にする