tozangezan's diary

勝手にソースコードをコピペして利用しないでください。

CODE FESTIVAL 2014 上海  2日目

あとでAdventarでいろいろします

6位でした。Eでずっと嵌っていたので仕方ない。

A:
まあFA。早解きレーサーの意地。

#include<stdio.h>
#include<algorithm>
using namespace std;
int p10[7];
int main(){
	int a;
	p10[0]=1;
	for(int i=1;i<7;i++)p10[i]=p10[i-1]*10;
	scanf("%d",&a);
	int val=1;
	for(int i=0;i<a;i++)val*=10;
	val--;
	printf("%d\n",val);
	for(int i=0;i<=val;i++){
		for(int j=0;j<a;j++){
			if(i/p10[a-j]%2)printf("%d",9-i%p10[a-j]/p10[a-j-1]);
			else printf("%d",i%p10[a-j]/p10[a-j-1]);
		}
		printf("\n");
	}
}

B:
まあFA。

#include<stdio.h>
#include<math.h>
#include<algorithm>
using namespace std;
long long ABS(long long a){return max(a,-a);}
int main(){
	int a;scanf("%d",&a);
	while(a--){
		long long b;scanf("%lld",&b);
		b--;
		long long t=(long long)sqrt((double)b/2);
		long long n=0;
		for(int i=-10;i<=10;i++){
			if(t+i<0)continue;
			n=t+i;
			if(1+(t+i)*(t+i+1)*2>b)break;
		}
		long long v=b-(1+(n-1)*(n)*2);
		long long x=-n+(v+1)/2;
		long long y=n-ABS(x);
		if(v%2)y=-y;
		printf("%lld %lld\n",x,y);
	}
}

C:
regular polygonの意味が分からなくてClarに出るまで解かなかった。それが解決すれば既出というか超典型。

#include<stdio.h>
#include<algorithm>
#include<set>
using namespace std;
int x[1100];
int y[1100];
int out[6];
set<pair<int,int> >S;
int main(){
	int a;
	scanf("%d",&a);
	for(int i=0;i<a;i++)scanf("%d%d",x+i,y+i);
	for(int i=0;i<a;i++)S.insert(make_pair(x[i],y[i]));
	
	for(int i=0;i<a;i++){
		for(int j=0;j<a;j++){
			if(i==j)continue;
			int X=x[j];
			int Y=y[j];
			int dx=x[j]-x[i];
			int dy=y[j]-y[i];
			X-=dy;
			Y+=dx;
			if(!S.count(make_pair(X,Y)))continue;
			X-=dx;
			Y-=dy;
			if(!S.count(make_pair(X,Y)))continue;
			out[0]=i+1;
			out[1]=j+1;
			for(int k=0;k<a;k++){
				if(x[k]==x[j]-dy&&y[k]==y[j]+dx)out[2]=k+1;
				if(x[k]==x[i]-dy&&y[k]==y[i]+dx)out[3]=k+1;
				
			}
			std::sort(out,out+4);
			printf("4\n");
			for(int k=0;k<4;k++)printf("%d\n",out[k]);
			return 0;
		}
	}printf("0\n");
}

D:
フロー復元するだけ。

#include<stdio.h>
#include<vector>
#include<string.h>
#include<queue>
#include<algorithm>
using namespace std;
namespace MCF {
	
}
int dx[]={1,0,-1,0};
int dy[]={0,1,0,-1};
char str[100][100];
int bfs[100][100];
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<100;i++)for(int j=0;j<100;j++)bfs[i][j]=-1;
	queue<pair<int,int> > Q;
	int sr,sc;
	int ar,ac;
	int br,bc;
	for(int i=0;i<a;i++)for(int j=0;j<b;j++){
		if(str[i][j]=='S'){sr=i;sc=j;}
		if(str[i][j]=='A'){ar=i;ac=j;}
		if(str[i][j]=='B'){br=i;bc=j;}
	}
	Q.push(make_pair(sr,sc));
	bfs[sr][sc]=0;
	while(Q.size()){
		int row=Q.front().first;
		int col=Q.front().second;
		Q.pop();
		for(int i=0;i<4;i++){
			if(0<=row+dx[i]&&row+dx[i]<a&&0<=col+dy[i]&&col+dy[i]<b&&!~bfs[row+dx[i]][col+dy[i]]&&str[row+dx[i]][col+dy[i]]!='#'){
				bfs[row+dx[i]][col+dy[i]]=bfs[row][col]+1;
				Q.push(make_pair(row+dx[i],col+dy[i]));
			}
		}
	}
	int ad=bfs[ar][ac];
	int bd=bfs[br][bc];
	MCF::init(a*b*2+1);
	for(int i=0;i<a;i++)for(int j=0;j<b;j++){
		MCF::ae(2*(i*b+j),2*(i*b+j)+1,1,0);
		for(int k=0;k<4;k++){
			if(0<=i+dx[k]&&i+dx[k]<a&&0<=j+dy[k]&&j+dy[k]<b&&str[i+dx[k]][j+dy[k]]!='#'){
				MCF::ae(2*(i*b+j)+1,2*((i+dx[k])*b+j+dy[k]),1,1);
			}
		}
	}
	MCF::ae(2*(ar*b+ac)+1,a*b*2,1,0);
	MCF::ae(2*(br*b+bc)+1,a*b*2,1,0);
	int res=MCF::solve(2*(sr*b+sc)+1,a*b*2,2);
	if(!res||MCF::toc>ad+bd){
		printf("NA\n");return 0;
	}
	int nr=ar;
	int nc=ac;
	while(1){
		int t=2*(nr*b+nc);
		int to;
		for(int i=MCF::ptr[t];~i;i=MCF::next[i]){
			if(MCF::col[i]&&MCF::capa[i]){
				to=MCF::zu[i]/2;
				break;
			}
		}
		int tr=to/b;
		int tc=to%b;
		if(sr==tr&&sc==tc)break;
		str[tr][tc]='a';
		nr=tr;nc=tc;
	}
	 nr=br;
	 nc=bc;
	while(1){
		int t=2*(nr*b+nc);
		int to;
		for(int i=MCF::ptr[t];~i;i=MCF::next[i]){
			if(MCF::col[i]&&MCF::capa[i]){
				to=MCF::zu[i]/2;
				break;
			}
		}
		int tr=to/b;
		int tc=to%b;
		if(sr==tr&&sc==tc)break;
		str[tr][tc]='b';
		nr=tr;nc=tc;
	}
	for(int i=0;i<a;i++)printf("%s\n",str[i]);
}

E:
81は定数みたいなものだから…(Mountain解説参照)
定数倍改善しようとしていて嵌った。結局3^4を消して解決した。

#include<stdio.h>
#include<algorithm>
using namespace std;
double dp[110][110][110][4];
double p[3];
int a,b,c;
bool de=false;
double solve(int P,int q,int r,int v){
	if(dp[P][q][r][v]>-0.5)return dp[P][q][r][v];
	if(P==0&&q==0&&r==0)return dp[P][q][r][v]=0;
	double ret=999999999;
	for(int i=0;i<3;i++){
		int X=P;int Y=q;int Z=r;
		if(i==0)X--;
		if(i==1)Y--;
		if(i==2)Z--;
		double val=0;
		double dame=0;
		if(X<0||Y<0||Z<0){
			if(v==0)continue;
		}
		if(v==0){
			ret=min(ret,(solve(X,Y,Z,v+1)*p[i]+1)/(p[i]));
		}else if((v==2&&i==0)||v==3){
			ret=min(ret,(solve(max(X,0),max(Y,0),max(Z,0),0)*p[i]+solve(P,q,r,0)*(1.0-p[i])));
		}else{
			ret=min(ret,(solve(max(X,0),max(Y,0),max(Z,0),v+1)*p[i]+solve(P,q,r,0)*(1.0-p[i])));
		}
	}
	return dp[P][q][r][v]=ret;
}
int main(){
	int d,e,f;
	scanf("%d%d%d%d%d%d",&a,&b,&c,&d,&e,&f);
	p[0]=0.01*d;
	p[1]=0.01*e;
	p[2]=0.01*f;
	
	for(int i=0;i<110;i++)for(int j=0;j<110;j++)for(int k=0;k<110;k++)
		for(int l=0;l<4;l++)dp[i][j][k][l]=-1.0;
	printf("%.12f\n",solve(a,b,c,0));
}

F:
ほんとこれすき。
累積積をここまでうまく出せるの尊敬する。
頭が悪くて&一度積segtree書いてみたくてsegtree書いてた

#include<stdio.h>
#include<algorithm>
using namespace std;
int s[110000];
int t[110000];
double p[110000];
double q[110000];
double segtree[524288];
void update(int a,double b){
	a+=262144;
	while(a){
		segtree[a]*=b;
		a/=2;
	}
}
double query(int a,int b,int c,int d,int e){
	if(d<a||b<c)return 1;
	if(c<=a&&b<=d)return segtree[e];
	return query(a,(a+b)/2,c,d,e*2)*query((a+b)/2+1,b,c,d,e*2+1);
}
pair<int,pair<int,int> >ev[210000];
int S[110000];
int T[110000];
int main(){
	int a;
	scanf("%d",&a);
	for(int i=0;i<a;i++){
		scanf("%d%d",s+i,t+i);
		ev[i*2]=make_pair(s[i],make_pair(i,0));
		ev[i*2+1]=make_pair(t[i],make_pair(i,1));
	}
	std::sort(ev,ev+a*2);
	for(int i=0;i<524288;i++)segtree[i]=1;
	for(int i=0;i<a*2;i++){
		if(ev[i].second.second==0)S[ev[i].second.first]=i;
		if(ev[i].second.second==1)T[ev[i].second.first]=i;
	}
	int now=0;
	for(int i=0;i<a*2;i++){
		if(ev[i].second.second==0){
			now++;
		}else{
			update(i,1.0-1.0/now);
			now--;
		}
	}
	for(int i=0;i<a;i++){
		double P=query(0,262143,S[i],T[i]-1,1);
		double Q=query(0,262143,S[i],T[i],1);
		printf("%.12f %.12f\n",1.0-P,Q);
	}
}