tozangezan's diary

勝手にソースコードをコピペして利用しないでください。

今日解いた問題たち⑤

今日はCodeforcesの問題を解くのをお休みにして、Readforcesの問題を解くことにしました。

229C - Triangles
問題文を読み間違えていた。正しく読めば簡単。
Knの三角形はnC3個。
ここからm辺取り除くとまずm*(n-2)個の三角形が消え、包除原理で頂点を共有する2辺の組の数だけ三角形が増え、取り除く辺でできる
三角形の個数だけ減る。
もう1つでは取り除く辺で出来る三角形の個数だけを考える。
ということは、和はnC3-m*(n-2)+(包除原理で頂点を共有する2辺の組の数だけ三角形が増え)で求まるので楽。
nC3をnC2にしていた。

#include<stdio.h>
#include<algorithm>
using namespace std;
int c[1000000];
int d[1000000];
int e[1000000];
int main(){
	int a,b;
	scanf("%d%d",&a,&b);
	for(int i=0;i<b;i++)scanf("%d%d",c+i,d+i);
	long long ret=(long long)a*(a-1)*(a-2)/6-(long long)b*(a-2);
	for(int i=0;i<b;i++){
		e[c[i]-1]++;
		e[d[i]-1]++;
	}
	for(int i=0;i<a;i++)ret+=(long long)e[i]*(e[i]-1)/2;
	printf("%I64d\n",ret);
}

258B - Little Elephant and Elections
正直英語が難しすぎて読めない。が、問題の概要を教えてもらったとおりにコンビネーション計算すれば通る。
面倒すぎる。これでもBなのか…CFこわ……

#include<stdio.h>
#include<algorithm>
using namespace std;
int b[6];
int c[5];
int r[20];
int perm[14];
int s[10];
int main(){
	int a;
	scanf("%d",&a);
	int t=a/100000;
	for(int i=0;i<100000;i++){
		int d=i;
		int e=0;
		while(d){
			if(d%10==4||d%10==7)e++;
			d/=10;
		}
		b[e]++;
	}
	for(int i=0;i<t;i++){
		int d=i;
		int e=0;
		while(d){
			if(d%10==4||d%10==7)e++;
			d/=10;
		}
		c[e]++;
	}
	for(int i=0;i<6;i++){
		for(int j=0;j<5;j++){
			r[i+j]+=b[i]*c[j];
		}
	}
	for(int i=t*100000;i<=a;i++){
		int d=i;
		int e=0;
		while(d){
			if(d%10==4||d%10==7)e++;
			d/=10;
		}
		r[e]++;
	}
	r[0]--;
	int v=0;
	int mod=1000000007;
	long long ret=0;
	for(int i=8;i<14;i++){
		perm[i]=1;
	}
	do{
		long long now=1;
		int n=0;
		int m=0;
		for(int i=0;i<10;i++)s[i]=0;
		int x=0;
		for(int i=0;i<14;i++){
			if(perm[i]){
				now=now*(r[n]-s[n])%mod;
				s[n]++;
				n=0;
				x++;
				if(x==6)break;
			}else {n++;m++;}
		}
		int K=0;
		for(int i=m+1;i<10;i++)K+=r[i];
		now=now*K%mod;
		ret=(ret+now)%mod;
	}while(next_permutation(perm,perm+14));
	printf("%d\n",(int)ret);
}

121C - Lucky Permutation
問題を読み間違えました。(本日3回連続3回目)
場所iにあるiがlucky numberな個数なのではなく、lucky numberな場所iにある数がlucky numberな物を答えるらしい。
最後の13個以外はk番目の順列に全く関係ないので、ここだけ別に数えればよいです。これも面倒すぎる。

#include<stdio.h>
#include<algorithm>
using namespace std;
int fact[]={1,1,2,6,24,120,720,5040,40320,362880,3628800,39916800,479001600};
int perm[13];
int used[13];
int main(){
	int a,b;
	scanf("%d%d",&a,&b);
	if(a<13&&b>fact[a]){
		printf("-1\n");
		return 0;
	}
	int c=max(1,a-12);
	int ret=0;
	for(int i=1;i<=9;i++){
		for(int j=0;j<(1<<i);j++){
			int now=0;
			for(int k=0;k<i;k++){
				now*=10;
				if(j&(1<<k))now+=4;
				else now+=7;
			}
			if(now<c)ret++;
		}
	}
	int p=min(13,a);
	b--;
	for(int i=0;i<p;i++){
		int d=b/fact[p-i-1];
	//	printf("%d\n",d);
	//	fflush(stdout);
		b%=fact[p-i-1];
		int at=0;
		int e=d+1;
		while(1){
			if(!used[at])e--;
			if(e==0)break;
			at++;
		}
		used[at]=1;
		perm[i]=at;
	}
	for(int i=0;i<p;i++){
			int k=c+i;
			bool ok=true;
			while(k){
				if(k%10!=4&&k%10!=7)ok=false;
				k/=10;
			}
			k=c+perm[i];
			while(k){
				if(k%10!=4&&k%10!=7)ok=false;
				k/=10;
			}
			if(ok)ret++;
	}
	printf("%d\n",ret);
}