今日解いた問題たち⑤
今日は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); }