今日解いた問題たち③

今日も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]);
}