AOJ 2446,1161

今日はあまり難しい問題が解けなかった…あさって模擬国内なのに……（絶望）

2446
罠が多い。へんなDPでほうじょ原理をする。これLCMがlong longに収まらないの大迷惑なんだが…

#include<stdio.h>
#include<algorithm>
using namespace std;
long long dp[1<<20];
long long c[20];
int d[20];
long long gcd(long long a,long long b){
	while(a){
		b%=a;
		long long C=a;
		a=b;
		b=C;
	}
	return b;
}
long long ABS(long long a){return max(a,-a);}
int main(){
	int a;
	long long b;
	scanf("%d%lld",&a,&b);
	for(int i=0;i<a;i++)scanf("%lld",c+i);
	for(int i=0;i<a;i++)scanf("%d",d+i);
	for(int i=1;i<(1<<a);i++){
		long long GCD=0LL;
		long long m=1;
		for(int j=0;j<a;j++){
			if(i&(1<<j)){
				GCD=gcd(m,c[j]);
				double lcm=(double)m/GCD*c[j];
				if(lcm>(double)b+0.001){
					m=b+1;break;
				}else m=m/GCD*c[j];
			}
		}
		dp[i]=b/m;
	}
	for(int i=0;i<a;i++)
		for(int j=0;j<(1<<a);j++)
			if(j&(1<<i))dp[j]-=dp[j^(1<<i)];
	double ret=0;
	for(int i=0;i<(1<<a);i++){
		double p=1;
		for(int j=0;j<a;j++)if(i&(1<<j))p*=0.01*d[j];else p*=0.01*(100-d[j]);
		ret+=p*(ABS(dp[i]));
	}
	printf("%.9f\n",ret);
}

1161
やるだけ。

#include<stdio.h>
#include<algorithm>
#include<string.h>
using namespace std;
int perm[10];
int p[26];
int q[26];
int f[26];
int u[26];
char str[10];
int main(){
	int a;
	while(scanf("%d",&a),a){
		for(int i=0;i<26;i++)
			p[i]=q[i]=f[i]=u[i]=0;
		for(int i=0;i<a;i++){
			scanf("%s",str);
			int len=strlen(str);
			if(len!=1)f[str[0]-'A']=1;
			int ad=1;
			for(int j=len-1;j>=0;j--){
				if(i<a-1)p[str[j]-'A']+=ad;
				else q[str[j]-'A']+=ad;
				ad*=10;
			}
		}
		int n=0;
		for(int i=0;i<26;i++)if(p[i]||q[i]){
			u[n++]=i;
		}
		//for(int i=0;i<n;i++)printf("%d ",p[u[i]]);
		for(int i=0;i<10;i++)perm[i]=0;
		for(int i=0;i<n;i++)perm[9-i]=n-i;
		int ret=0;
		do{
			bool ok=true;
			if(perm[0]&&f[u[perm[0]-1]])ok=false;
			int val=0;
			int A=0;
			for(int i=0;i<10;i++)if(perm[i]){val+=i*p[u[perm[i]-1]];A+=i*q[u[perm[i]-1]];}
			if(val!=A)ok=false;
			if(ok)ret++;
		}while(next_permutation(perm,perm+10));
		printf("%d\n",ret);
	}
}

そういやAOJのshortest codeの数でソートしたランキングサイトってどこにあるんだっけ