今日解いた問題たち①

今日は簡単な順にcombinatoricsを埋めています。

Solvedの多い問題からCombinatoricsを埋めていきます。

131C - The World is a Theatre
コンビネーションの掛け算やるだけ。

#include<stdio.h>
long long C[61][61];
int main(){
	int a,b,c;
	scanf("%d%d%d",&a,&b,&c);
	C[0][0]=1;
	for(int i=0;i<60;i++){
		for(int j=0;j<=i;j++){
			C[i+1][j]+=C[i][j];
			C[i+1][j+1]+=C[i][j];
		}
	}
	long long ret=C[a+b][c];
	for(int i=0;i<4;i++)ret-=C[a][i]*C[b][c-i];
	ret-=C[a][c];
	printf("%I64d\n",ret);
}

322B - Ciel and Flowers
Div2Bにしては難しすぎでは…　場合わけするだけ。*1

#include<stdio.h>
int main(){
	unsigned int a,b,c;
	scanf("%u%u%u",&a,&b,&c);
	if(((a%3+b%3+c%3==4&&(a==0||b==0||c==0))||a%3+b%3+c%3==3)&&(a%3)*(b%3)*(c%3)==0){
		printf("%u\n",(a+b+c)/3-1);
	}
	else printf("%u\n",(a+b+c)/3);
}

152C - Pocket Book
掛け算するだけ。

#include<stdio.h>
char str[128];
int v[128][26];
int main(){
	int mod=1000000007;
	int a,b;
	scanf("%d%d",&a,&b);
	for(int i=0;i<a;i++){
		scanf("%s",str);
		for(int j=0;j<b;j++)v[j][str[j]-'A']++;
	}
	long long ret=1;
	for(int i=0;i<b;i++){
		int count=0;
		for(int j=0;j<26;j++)if(v[i][j])count++;
		ret=ret*count%mod;
	}
	printf("%d\n",ret);
}

327C - Magic Five
逆元とか累乗数とかを沢山掛け算する。面倒。

#include<stdio.h>
#include<string.h>
char str[100001];
int main(){
	int mod=1000000007;
	int b;
	scanf("%s%d",str,&b);
	int a=strlen(str);
	long long c=mod-2;
	long long d=1;
	long long e=1;
	for(int i=0;i<a;i++)e=e*2%mod;
	e--;
	while(c){
		if(c%2){
			d=d*e%mod;
		}
		e=e*e%mod;
		c/=2;
	}
	long long rev=d;
	c=(long long)a*b;
	d=1;
	e=2;
	while(c){
		if(c%2){
			d=d*e%mod;
		}
		e=e*e%mod;
		c/=2;
	}
	d--;
	d=d*rev%mod;
	long long p=0;
	long long q=1;
	for(int i=0;i<a;i++){
		if(str[i]=='0'||str[i]=='5')p=(p+q)%mod;
		q=q*2%mod;
	}
	printf("%d\n",p*d%mod);
}

124B - Permutations
やるだけ。テストケース多すぎでは…

#include<stdio.h>
#include<algorithm>
using namespace std;
int perm[8];
char str[8][9];
int main(){
	int a,b;
	scanf("%d%d",&a,&b);
	for(int i=0;i<a;i++)scanf("%s",str[i]);
	for(int i=0;i<b;i++)perm[i]=i;
	int ret=999999999;
	do{
		int l=999999999;
		int r=0;
		for(int i=0;i<a;i++){
			int c=0;
			for(int j=0;j<b;j++){
				c*=10;
				c+=str[i][perm[j]]-'0';
			}
			r=max(c,r);
			l=min(c,l);
		}
		ret=min(ret,r-l);
	}while(next_permutation(perm,perm+b));
	printf("%d\n",ret);
}

300C - Beautiful Numbers

面倒だし、制約の数字が読めないのでREする。ついでにオーバーフローしてないのにマイナスの値になる。
やっぱりCodeforcesは苦手…

#include<stdio.h>
long long mod=1000000007;
long long rev[1000002];
int main(){
	int a,b,c;
	scanf("%d%d%d",&a,&b,&c);
	rev[1]=1;
	for(int i=2;i<1000002;i++)rev[i]=mod-(mod/i)*rev[mod%i]%mod;
	long long ret=0;
	long long now=1;
	for(int i=0;i<=c;i++){
		int d=i*a+(c-i)*b;
		bool ok=true;
		while(d){
			if(d%10!=a&&d%10!=b)ok=false;
			d/=10;
		}
		if(ok)ret=(ret+now)%mod;
		now=now*(c-i)%mod*rev[i+1]%mod;
	}
	printf("%I64d\n",ret);
}

251A,252C - Points on Line
尺取して数えるだけ。

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

*1:WAしました