今日もcombinatorics埋めていきます。
319A - Malek Dance Club
難しそうだが考えたら独立だった。
#include<stdio.h> #include<algorithm> #include<string.h> using namespace std; char str[128]; int main(){ scanf("%s",str); int mod=1000000007; int n=strlen(str); int ret=0; for(int i=0;i<n;i++){ if(str[i]=='1'){ int now=1; for(int j=0;j<2*n-i-2;j++){ now=now*2%mod; } ret=(ret+now)%mod; } }printf("%d\n",ret); }
340C - Tourist Problem
規則を探しました。入力ソートされてなかった・・・
#include<stdio.h> #include<algorithm> using namespace std; long long gcd(long long a,long long b){ while(a){ b%=a; long long c=a; a=b; b=c; } return b; } int t[100001]; int main(){ int a; scanf("%d",&a); for(int i=0;i<a;i++)scanf("%d",t+i+1); std::sort(t,t+a+1); long long dis=0; for(int i=0;i<a;i++){ dis+=(long long)(i*2+1)*(a-i)*(t[i+1]-t[i]); } long long p=gcd(dis,a); printf("%I64d %I64d\n",dis/p,a/p); }
232A - Cycles
激ムズDiv1A。CombinatoricsのDiv1Aでは最強。
こうやって作りました。
まず、微妙に目標を超える完全グラフを作る。(ぴったりならぴったりで終わりにしてよい)
削る。削るとき、iとi+1を結ぶ辺を(他と干渉しないように)とりのぞくとn-2個三角形が減る。
微妙に目標より多く削る。(ここで86頂点使う)
もう一度同じことをする。(ここで9頂点使う)
最後に微調整。5頂点で1~6が作れればよい。これは全部手で作る。あとは打ち込んで終わり。
打ち込むときに3はあとで書こう~ と思って実際に書く前に提出してしまいました!!!!
#include<stdio.h> #include<algorithm> using namespace std; char out[100][101]; int main(){ for(int i=0;i<100;i++) for(int j=0;j<100;j++) out[i][j]='0'; int a; scanf("%d",&a); int n=3; while(n*(n-1)*(n-2)/6<a)n++; int d=n*(n-1)*(n-2)/6-a; for(int i=0;i<n;i++) for(int j=0;j<n;j++) out[i][j]=(i!=j?'1':'0'); int at=0; while(d>0){ out[at][at+1]=out[at+1][at]='0'; at+=2; d-=n-2; } d=-d; if(d){ int m=3; while(m*(m-1)*(m-2)/6<d)m++; int e=m*(m-1)*(m-2)/6-d; for(int i=0;i<m;i++) for(int j=0;j<m;j++) out[n+i][n+j]=(i!=j?'1':'0'); at=0; while(e>0){ out[n+at][n+at+1]=out[n+at+1][n+at]='0'; at+=2; e-=m-2; } e=-e; int S=n+m; switch(e){ case 3: out[S+1][S+4]=out[S+2][S+4]=out[S+4][S+2]=out[S+4][S+1]='1'; case 2: out[S][S+3]=out[S+1][S+3]=out[S+3][S]=out[S+3][S+1]='1'; case 1: out[S][S+1]=out[S+1][S]=out[S+2][S]=out[S][S+2]=out[S+1][S+2]=out[S+2][S+1]='1'; break; case 7: out[S+2][S+4]=out[S+4][S+2]='1'; case 5: out[S][S+4]=out[S+1][S+4]=out[S+4][S]=out[S+4][S+1]='1'; case 4: out[S][S+3]=out[S+1][S+3]=out[S+3][S]=out[S+3][S+1]=out[S+2][S+3]=out[S+3][S+2]='1'; out[S][S+1]=out[S+1][S]=out[S+2][S]=out[S][S+2]=out[S+1][S+2]=out[S+2][S+1]='1'; break; case 6: out[S][S+1]=out[S][S+2]=out[S][S+3]=out[S][S+4]=out[S+1][S]=out[S+2][S]=out[S+3][S]=out[S+4][S]='1'; out[S+2][S+1]=out[S+1][S+2]=out[S+2][S+3]=out[S+3][S+4]=out[S+1][S+3]=out[S+3][S+1]=out[S+3][S+2]=out[S+4][S+3]='1'; break; } } printf("100\n"); for(int i=0;i<100;i++)printf("%s\n",out[i]); }