読者です 読者をやめる 読者になる 読者になる

ひとり地区予選 SEERC 2015

yosupot と kyuridenamidaの3人でやりました(チームではない)。

F:
試し割りをするだけ

#include<stdio.h>
#include<algorithm>
using namespace std;
long long t[110];
long long s[110];
long long u[110];
int main(){
	int a;scanf("%d",&a);
	for(int i=0;i<a;i++){
		scanf("%lld",&t[a-1-i]);
	}
	t[a]=1;
	int cnt=a;
	for(int r=-10;r<=10;r++){
		while(cnt){
			for(int i=0;i<10;i++){
				s[i]=t[i];
				u[i]=0;
			}
			for(int i=cnt;i>0;i--){
				long long ks=s[i];
				u[i-1]=ks;
				s[i-1]-=ks*r;
			}
			if(s[0]==0){
				cnt--;
				for(int i=0;i<10;i++)t[i]=u[i];
			}else break;
		}
		/*for(int i=0;i<=cnt;i++){
			printf("%lld ",t[cnt-i]);
		}printf("\n");*/
	}
	printf("%d\n",cnt);
}

I:
メモリ制限が4MBなことに気づかず
気づいたらやるだけ

#include<stdio.h>
#include<algorithm>
using namespace std;
int c[110000];
int d[110000];
int main(){
	int a,b;scanf("%d%d",&a,&b);
	for(int i=0;i<a;i++){
		int e;scanf("%d",&e);
		c[e/10000]++;
		d[e%10000]++;
	}
	int ret=0;
	for(int i=0;i<=100000;i++)if(c[i]%b)ret=i*10000;
	for(int i=0;i<10000;i++)if(d[i]%b)ret+=i;
	printf("%d\n",ret);
}

D:
適当に数論する

#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;
}
long long lcm(long long a,long long b){
	return a/gcd(a,b)*b;
}
int main(){
	int a,b;scanf("%d%d",&a,&b);
	if(a>b)swap(a,b);
	if(a==b){
		printf("1\n");return 0;
	}
	int c=b-a;
	long long ret=-1;
	int ans=1000000007;
	for(int i=1;i*i<=c;i++){
		if(c%i==0){
			int n=(i-a%i);
			long long tmp=lcm(a+n,b+n);
			if(ret==-1||ret>tmp||(ret==tmp&&ans>n)){
				ret=tmp;ans=n;
			}
			
			n=(c/i-a%(c/i));
			tmp=lcm(a+n,b+n);
			if(ret==-1||ret>tmp||(ret==tmp&&ans>n)){
				ret=tmp;ans=n;
			}
		}
	}
	printf("%d\n",ans);
}

B:
Heavy-Light Decomposition + 平方分割
Do useをコピペした

#include<stdio.h>
#include<algorithm>
#include<vector>
#include<queue>
#define BEGIN_STACK_EXTEND(size) void * stack_extend_memory_ = malloc(size);void * stack_extend_origin_memory_;char * stack_extend_dummy_memory_ = (char*)alloca((1+(int)(((long long)stack_extend_memory_)&127))*16);*stack_extend_dummy_memory_ = 0;asm volatile("mov %%rsp, %%rbx\nmov %%rax, %%rsp":"=b"(stack_extend_origin_memory_):"a"((char*)stack_extend_memory_+(size)-1024));
#define END_STACK_EXTEND asm volatile("mov %%rax, %%rsp"::"a"(stack_extend_origin_memory_));free(stack_extend_memory_);
using namespace std;
int c[510000];
int sz[510000];
int eu[1010000];
int conv[510000];
int rev[510000];
vector<int>g[510000];
int L[510000];
int par[510000];
int str[510000];
int ww[510000];
int wn[510000];
int SQ=500;
int cur;
int cur2;
void dfs(int a,int b){
	par[a]=b;
	conv[a]=cur;
	rev[cur]=a;
	cur++;
	L[a]=cur2;
	eu[cur2++]=a;
	sz[a]=1;
	str[a]=-1;
	for(int i=0;i<g[a].size();i++){
		if(g[a][i]==b)continue;
		dfs(g[a][i],a);
		eu[cur2++]=a;
		sz[a]+=sz[g[a][i]];
		if(str[a]==-1||sz[str[a]]<sz[g[a][i]]){
			str[a]=g[a][i];
		}
	}
	if(sz[str[a]]*2<sz[a])str[a]=-1;
}
struct wolf{
	vector<int> node;
	vector<long long>val;
	vector<long long>sq;
	int par;
	int at;
	wolf(){
		par=at=-1;
	}
};
long long mod=1000000007;
long long inf=(long long)mod*mod;
vector<wolf> hl;

int lcaseg[2097152];
int lcaupd(int a,int b){
	a+=1048576;
	while(a){
		lcaseg[a]=min(lcaseg[a],b);
		a/=2;
	}
}
int lcamin(int a,int b,int c,int d,int e){
	if(d<a||b<c)return mod;
	if(c<=a&&b<=d)return lcaseg[e];
	return min(lcamin(a,(a+b)/2,c,d,e*2),lcamin((a+b)/2+1,b,c,d,e*2+1));
}
int main(){
//	BEGIN_STACK_EXTEND(250*1024*1024)
	int a,b;
	scanf("%d",&a);
	for(int i=0;i<a-1;i++){
		int p,q;
		scanf("%d%d",&p,&q);
		g[p].push_back(q);
		g[q].push_back(p);
	}
	for(int i=0;i<a;i++)scanf("%lld",c+i);
	dfs(0,-1);
	hl.push_back(wolf());
	hl[0].node.push_back(0);
	queue<pair<int,int> >Q;
	Q.push(make_pair(0,0));
	ww[0]=wn[0]=0;
	while(Q.size()){
		int at=Q.front().first;
		int seq=Q.front().second;
		Q.pop();
		for(int i=0;i<g[at].size();i++){
			if(g[at][i]==par[at])continue;
			if(str[at]==g[at][i]){
				ww[g[at][i]]=seq;
				wn[g[at][i]]=hl[seq].node.size();
				hl[seq].node.push_back(g[at][i]);
				Q.push(make_pair(g[at][i],seq));
			}else{
				Q.push(make_pair(g[at][i],hl.size()));
				ww[g[at][i]]=hl.size();
				wn[g[at][i]]=0;
				hl.push_back(wolf());
				hl[hl.size()-1].node.push_back(g[at][i]);
				hl[hl.size()-1].par=seq;
				hl[hl.size()-1].at=wn[at];
			}
		}
	}
	
	for(int i=0;i<2097152;i++)lcaseg[i]=mod;
	for(int i=0;i<cur2;i++){
		lcaupd(i,conv[eu[i]]);
	}
	for(int i=0;i<hl.size();i++){
		int sz=hl[i].node.size();
		hl[i].val=vector<long long>(sz);
		hl[i].sq=vector<long long>((sz+SQ-1)/SQ);
		for(int j=0;j<sz;j++){
			hl[i].val[j]=c[hl[i].node[j]];
			hl[i].sq[j/SQ]+=c[hl[i].node[j]];
		}
	}
//	for(int i=0;i<a;i++)printf("%d %d\n",ww[i],wn[i]);
	scanf("%d",&b);
	while(b--){
		int K,u,v;
		long long x,y,A,B,C,D;
		scanf("%d%lld%lld%lld%lld%lld%lld%d%d",&K,&x,&y,&A,&B,&C,&D,&u,&v);
		int q=u;
		int r=v;
		if(L[q]>L[r])swap(q,r);
		int lca=rev[lcamin(0,1048575,L[q],L[r],1)];
		int goal=ww[lca];
		vector<pair<int,pair<int,int> > >ql;
		vector<pair<int,pair<int,int> > >qr;
		if(goal==ww[q]){
			ql.push_back(make_pair(goal,make_pair(wn[q],wn[lca])));
		}else{
			ql.push_back(make_pair(ww[q],make_pair(wn[q],0)));
			int now=hl[ww[q]].par;
			int at=hl[ww[q]].at;
			while(now!=goal){
				ql.push_back(make_pair(now,make_pair(at,0)));
				at=hl[now].at;
				now=hl[now].par;
			}
			ql.push_back(make_pair(goal,make_pair(at,wn[lca])));
		}
		
		if(goal==ww[r]){
			if(r!=lca)qr.push_back(make_pair(goal,make_pair(wn[r],wn[lca]+1)));
		}else{
			qr.push_back(make_pair(ww[r],make_pair(wn[r],0)));
			int now=hl[ww[r]].par;
			int at=hl[ww[r]].at;
			while(now!=goal){
				qr.push_back(make_pair(now,make_pair(at,0)));
				at=hl[now].at;
				now=hl[now].par;
			}
			if(at!=wn[lca])qr.push_back(make_pair(goal,make_pair(at,wn[lca]+1)));
		}
		if(qr.size()){
			for(int i=qr.size()-1;i>=0;i--){
				swap(qr[i].second.first,qr[i].second.second);
				ql.push_back(qr[i]);
			}
		}
	//	printf("\n");
	//	for(int i=0;i<ql.size();i++){
	//		printf("%d (%d, %d)\n",ql[i].first,ql[i].second.first,ql[i].second.second);
	//	}
		for(int i=0;i<K;i++){
			hl[ww[x]].val[wn[x]]+=y;
			hl[ww[x]].sq[wn[x]/SQ]+=y;
			x=(A*x+B)%a;
			y=(C*y+D)%mod;
		}
		long long ret=0;
		for(int i=0;i<ql.size();i++){
			if(ql[i].second.first>ql[i].second.second)swap(ql[i].second.first,ql[i].second.second);
			int p1=ql[i].second.first;
			int p2=ql[i].second.second;
			int z=ql[i].first;
			if(p1/SQ==p2/SQ){
				for(int j=p1;j<=p2;j++){
			//		printf("%d: %lld\n",hl[z].node[j],hl[z].val[j]);
					ret+=hl[z].val[j];
				}
			}else{
				for(int j=p1;j%SQ;j++)ret+=hl[z].val[j];
				for(int j=p2-p2%SQ;j<=p2;j++)ret+=hl[z].val[j];
				for(int j=(p1+SQ-1)/SQ;j<p2/SQ;j++)ret+=hl[z].sq[j];
			}
		}
		printf("%lld\n",ret);
	}
	//END_STACK_EXTEND
}

夕食を食べる。

H:
imos法とかいろんなのをつかって上手いこと計算量を抑える。

#include<stdio.h>
#include<algorithm>
#include<vector>
using namespace std;
int imos[11000];
vector<pair<int,int> > v[1100];
vector<int> w[1100];
typedef unsigned long long wolf;
wolf chk[16][11000];
int main(){
	int a,b,c;
	scanf("%d%d%d",&a,&b,&c);
	for(int i=0;i<c;i++){
		int p,q,r;
		scanf("%d%d%d",&p,&q,&r);
		p--;q--;r--;
		imos[q]++;
		imos[r]--;
		v[p].push_back(make_pair(q,1));
		v[p].push_back(make_pair(r,-1));
		w[p].push_back(q);
	}
	for(int i=0;i<a;i++)w[i].push_back(b-1);
	for(int i=0;i<a;i++)std::sort(v[i].begin(),v[i].end());
	for(int i=0;i<a;i++)std::sort(w[i].begin(),w[i].end());
	for(int i=0;i<b;i++){
		imos[i+1]+=imos[i];
	}
	for(int i=0;i<a;i++){
		int cnt=0;
		int at=0;
		for(int j=0;j<b;j++){
			while(at<v[i].size()&&v[i][at].first==j){
				cnt+=v[i][at].second;
				at++;
			}
			if(cnt==0){
				chk[i/64][j]+=(1LL<<(i%64));
			}
		}
	}
	int ret=0;
	int left=0;
	for(int i=0;i<b;i++){
		if(i&&imos[i-1]>=a){
			left=i;
		}
		ret+=i-left;
	}
	for(int i=0;i<b-1;i++){
		int tmp=0;
		for(int j=0;j<a;j++){
			if(!(chk[j/64][i]&(1LL<<j)))continue;
			int at=*(lower_bound(w[j].begin(),w[j].end(),i));
			tmp=max(tmp,at-i);
		}
		//printf("%d\n",tmp);
		ret-=tmp;
	}
	printf("%d\n",ret);
}

E:
DijkstraとかbitDPを多用するよくある問題。

#include<stdio.h>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
vector<pair<int,int> > g[21000];
int ijk[21000];
int v[21000];
int g2[20][20];
int lis[20];
int sc[1<<15];
int dp[1<<15][16];
int dp2[1<<15];
int main(){
	int a,b;
	scanf("%d%d",&a,&b);
	for(int i=0;i<b;i++){
		int p,q,r,s;
		scanf("%d%d%d%d",&p,&q,&r,&s);
		q--;r--;
		g[q].push_back(make_pair(r,s));
		if(p==2){
			g[r].push_back(make_pair(q,s));
		}
	}
	int T;
	scanf("%d",&T);
	int V,K;
	scanf("%d%d",&V,&K);
	lis[K]=V-1;
	for(int i=0;i<K;i++){
		scanf("%d",lis+i);
		lis[i]--;
	}
	for(int i=0;i<=K;i++){
		int st=lis[i];
		for(int j=0;j<a;j++){
			v[j]=0;ijk[j]=1010101010;
		}
		ijk[st]=0;
		priority_queue<pair<int,int> > Q;
		Q.push(make_pair(0,st));
		while(Q.size()){
			int at=Q.top().second;
			int cost=-Q.top().first;Q.pop();
			if(v[at])continue;
			v[at]=1;
			for(int j=0;j<g[at].size();j++){
				int to=g[at][j].first;
				int toc=cost+g[at][j].second;
				if(!v[to]&&ijk[to]>toc){
					ijk[to]=toc;
					Q.push(make_pair(-toc,to));
				}
			}
		}
		for(int j=0;j<=K;j++)g2[i][j]=ijk[lis[j]];
	}
	//for(int i=0;i<=K;i++)for(int j=0;j<=K;j++)printf("%d %d: %d\n",i,j,g2[i][j]);
	for(int i=0;i<(1<<K);i++)for(int j=0;j<=K;j++)dp[i][j]=1010101010;
	dp[0][K]=0;
	for(int i=0;i<(1<<K);i++){
		if(__builtin_popcount(i)>=4)continue;
		for(int j=0;j<=K;j++){
			for(int k=0;k<K;k++){
				if(i&(1<<k))continue;
				dp[i+(1<<k)][k]=min(dp[i+(1<<k)][k],dp[i][j]+g2[j][k]);
			}
		}
	}
	for(int i=0;i<(1<<K);i++)sc[i]=1010101010;
	for(int i=0;i<(1<<K);i++)for(int j=0;j<=K;j++)
		sc[i]=min(sc[i],dp[i][j]);
	//for(int i=0;i<(1<<K);i++)printf("%d: %d\n",i,sc[i]);
	for(int i=0;i<(1<<K);i++)dp2[i]=1010101010;
	dp2[0]=0;
	for(int i=0;i<(1<<K);i++){
		int rem=(1<<K)-1-i;
		int bit=rem;
		while(bit){
			if(__builtin_popcount(bit)<=4){
				dp2[i+bit]=min(dp2[i+bit],dp2[i]+sc[bit]+T);
			}
			bit=(bit-1)&rem;
		}
	}
	printf("%d\n",dp2[(1<<K)-1]);
}

風呂に入ってのんびりしてからCを書くも間に合わない。

アディショナルタイム(C):
素因数の指数の集合の個数が少ないので全部列挙してDP
うまくまとめないとTLEする。

#include<stdio.h>
#include<algorithm>
#include<vector>
#include<map>
using namespace std;
int p[110000];
int lis[110000];
map<vector<int>,int> m;
double dp[2000][34];
vector<vector<int> > v;
int use[20];
void dfs(long long now,int at,int r){
	long long tmp=now;
	if(at){
		vector<int>t;
		for(int i=0;i<at;i++)t.push_back(use[i]);
		m[t]=v.size();
		v.push_back(t);
	}
	for(int i=1;i<=r;i++){
		tmp*=lis[at];
		if(tmp>10000000000LL)break;
		use[at]=i;
		dfs(tmp,at+1,i);
	}
}
int C[21][21];
int tt[21];
int cnt;
int perm[40][40];
void dfs2(int a,int b,int ks){
	if(b==v[a].size()){
		vector<int>L;
		vector<int>R;

		for(int i=0;i<v[a].size();i++){
			if(tt[i])L.push_back(tt[i]);
			if(v[a][i]-tt[i])R.push_back(v[a][i]-tt[i]);
		}
		if(L.size()==0||R.size()==0)return;
		//if(v[a].size()==2&&v[a][0]==3&&v[a][1]==2){
		//	printf("%d: ",ks);
		//	for(int i=0;i<v[a].size();i++)printf("%d ",tt[i]);
		//	printf("\n");
		//}
		std::sort(L.begin(),L.end());reverse(L.begin(),L.end());
		std::sort(R.begin(),R.end());reverse(R.begin(),R.end());
		int j=m[L];int at=m[R];
		int lcnt=0;
		int rcnt=0;
		for(int k=0;k<v[j].size();k++)lcnt+=v[j][k];
		for(int k=0;k<v[at].size();k++)rcnt+=v[at][k];
		for(int k=0;k<lcnt;k++){
			for(int l=0;l<rcnt;l++){
				dp[a][max(k,l)+1]+=dp[j][k]*dp[at][l]*ks;
			}
		}
		cnt+=ks;
		return;
	}
	int to=b;
	for(int i=b+1;i<v[a].size();i++)if(v[a][i]==v[a][b])to=i;
	int len=to-b+1;
	for(int i=0;i<len;i++)perm[b][i]=0;
	for(int i=0;i<v[a][b];i++)perm[b][len+i]=1;
	do{
		int to=ks;
		int ch=0;
		int use=0;
		int n=len;
		int ind=0;
		for(int i=0;i<len+v[a][b];i++){
			if(perm[b][i]==1){
				ch++;
				if(use)to*=C[n][use];
				n-=use;
				use=0;
			}else{
				tt[b+ind++]=ch;use++;
			}
		}
		dfs2(a,b+len,to);
	}while(next_permutation(perm[b],perm[b]+len+v[a][b]));
}
int main(){
	C[0][0]=1;
	for(int i=0;i<20;i++){
		for(int j=0;j<=i;j++){
			C[i+1][j]+=C[i][j];
			C[i+1][j+1]+=C[i][j];
		}
	}
	p[0]=p[1]=-1;
	for(int i=2;i<110000;i++){
		if(p[i]==-1)continue;
		p[i]=1;
		for(int j=i+i;j<110000;j+=i)p[j]=-1;
	}
	int sz=0;
	for(int i=2;i<110000;i++){
		if(p[i]==1)lis[sz++]=i;
	}
	dfs(1,0,99999999);
	int n=v.size();
	dp[0][0]=1;
	int Q=0;
	for(int i=1;i<n;i++){
		cnt=0;
		dfs2(i,0,1);
		if(cnt)for(int j=0;j<34;j++)dp[i][j]/=cnt;
	}
	int T;scanf("%d",&T);
	while(T--){
		long long a;
		scanf("%lld",&a);
		vector<int>s;
		long long b=a;
		for(int i=0;(long long)lis[i]*lis[i]<=b;i++){
			if(b%lis[i]==0){
				int tmp=0;
				while(b%lis[i]==0){
					b/=lis[i];
					tmp++;
				}
				s.push_back(tmp);
			}
		}
		if(b>1)s.push_back(1);
		std::sort(s.begin(),s.end());
		reverse(s.begin(),s.end());
		int ind=m[s];
		double ret=0;
		for(int i=0;i<=33;i++){
			ret+=dp[ind][i]*i;
		}
		printf("%.12f\n",ret);
	}
}