tozangezan's diary

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

ひとり地区予選 2014-2015 ACM-ICPC East Central North America

何問解こうが虚無に5時間を費やしたことに変わりはないセット...

B: A Cure for the Common Code
10万回見たような設定の問題...。強引に高速化した区間DPするだけ。

char in[1100];
int dp[510][510];
int lg10[510];
int kr[510][510];
int solve(int a,int b){
	if(dp[a][b]!=-1)return dp[a][b];
	if(a==b)return dp[a][b]=0;
	int ret=mod;
	ret=min(ret,solve(a+1,b)+1);
	ret=min(ret,solve(a,b-1)+1);
	for(int i=a+1;i<b;i++){
		ret=min(ret,solve(a,i)+solve(i,b));
	}
	for(int i=1;i<b-a;i++){
		if((b-a)%i)continue;
		if(kr[a][i]>=b-a){
			if(i>1)ret=min(ret,solve(a,a+i)+2+lg10[(b-a)/i]);
			else ret=min(ret,solve(a,a+i)+lg10[(b-a)/i]);
		}
	}
	//printf("%d %d: %d\n",a,b,ret);
	return dp[a][b]=ret;
}
int main(){
	int ts=0;
	for(int i=1;i<510;i++){
		int c=i;
		while(c){
			lg10[i]++;c/=10;
		}
	}
	while(1){
		scanf("%s",in);
		if(in[0]=='0')break;
		int n=strlen(in);
		for(int i=0;i<=n;i++)for(int j=0;j<=n;j++){
			dp[i][j]=-1;
		}
		for(int i=0;i<510;i++)for(int j=0;j<510;j++)kr[i][j]=0;
		for(int i=0;i<n;i++){
			for(int j=1;j<=n;j++){
				for(int k=i;k<n;k++){
					if(k-j>=i&&in[k]!=in[k-j]){
						break;
					}
					kr[i][j]++;
				}
			}
		}
		ts++;
		printf("Case %d: %d\n",ts,solve(0,n));
	}
}

D: Generalized Roman Numerals
これも強引に区間DPを高速化するだけ...setのinsertは重いのでバカみたいにやってはいけない。

char in[1100];
set<int>dp[62][62];

void calc(int a,int b){
	if(a==b)return;
	if(dp[a][b].size())return;
	if(a+1==b){
		if(in[a]=='I')dp[a][b].insert(1);
		if(in[a]=='V')dp[a][b].insert(5);
		if(in[a]=='X')dp[a][b].insert(10);
		if(in[a]=='L')dp[a][b].insert(50);
		if(in[a]=='C')dp[a][b].insert(100);
		
		return;
	}
	vector<int>can(5001);
	for(int i=a+1;i<b;i++){
		calc(a,i);
		calc(i,b);
		for(set<int>::iterator it=dp[a][i].begin();it!=dp[a][i].end();it++){
			for(set<int>::iterator it2=dp[i][b].begin();it2!=dp[i][b].end();it2++){
				int A=*it;
				int B=*it2;

				if(A>=B)can[A+B]=1;
				else can[B-A]=1;
			}
		}
	}
	for(int i=0;i<5001;i++)if(can[i])dp[a][b].insert(i);
}
int main(){
	int ts=0;
	while(1){
		scanf("%s",in);
		if(in[0]=='0')break;
		int n=strlen(in);
		for(int i=0;i<62;i++)for(int j=0;j<62;j++)dp[i][j].clear();
		calc(0,n);
		ts++;
		printf("Case %d:",ts);
		for(set<int>::iterator it=dp[0][n].begin();it!=dp[0][n].end();it++){
			printf(" %d",*it);
		}
		printf("\n");
	}
}

A: Continued Fractions
連分数展開された有理数の四則演算をするだけ。負がある嫌がらせつき。

int p[2][20];
long long bs[2];
long long bb[2];
long long gcd(long long a,long long b){
	while(a){
		b%=a;swap(a,b);
	}
	return b;
}
void output(long long bs,long long bb){
	long long g=gcd(ABS(bs),ABS(bb));
	bs/=g;bb/=g;
	if(bb<0){
		bb=-bb;bs=-bs;
	}
	vector<long long>ans;
	if(bs>=0){
		ans.push_back(bs/bb);
		bs%=bb;
	}else{
		int gb=0;
		while(bs<0){
			gb++;
			bs+=bb;
		}
		ans.push_back(-gb);
	}
	while(bs){
		swap(bs,bb);
		ans.push_back(bs/bb);
		bs%=bb;
	}
	for(int i=0;i<ans.size();i++){
		if(i)printf(" ");
		printf("%I64d",ans[i]);
	}
	printf("\n");
}
int main(){
	int ts=0;
	while(1){
		int a,b;scanf("%d%d",&a,&b);
		if(a==0)break;
		for(int i=0;i<a;i++){
			scanf("%d",&p[0][i]);
		}
		for(int i=0;i<b;i++){
			scanf("%d",&p[1][i]);
		}
		if(a>2){
			bb[0]=p[0][a-1];bs[0]=1;
			for(int i=a-2;i>0;i--){
				long long tmp=bb[0];
				bb[0]=p[0][i]*bb[0]+bs[0];
				bs[0]=tmp;
			}
			bs[0]+=bb[0]*p[0][0];
		}else if(a==2){
			bb[0]=p[0][1];
			bs[0]=p[0][1]*p[0][0]+1;
		}else{
			bb[0]=1;bs[0]=p[0][0];
		}
		if(b>2){
			bb[1]=p[1][b-1];bs[1]=1;
			for(int i=b-2;i>0;i--){
				long long tmp=bb[1];
				bb[1]=p[1][i]*bb[1]+bs[1];
				bs[1]=tmp;
			}
			bs[1]+=bb[1]*p[1][0];
		}else if(b==2){
			bb[1]=p[1][1];
			bs[1]=p[1][1]*p[1][0]+1;
		}else{
			bb[1]=1;bs[1]=p[1][0];
		}
		
		ts++;
		printf("Case %d:\n",ts);
		output(bs[0]*bb[1]+bs[1]*bb[0],bb[0]*bb[1]);
		output(bs[0]*bb[1]-bs[1]*bb[0],bb[0]*bb[1]);
		output(bs[0]*bs[1],bb[0]*bb[1]);
		output(bs[0]*bb[1],bb[0]*bs[1]);
	}
}

H: Time Warp
ストレスしかたまらない算数。パソコン甲子園でやれ

char in[10];
int main(){
	int T;scanf("%d",&T);
	for(int t=1;t<=T;t++){
		int deg;
		int h;
		scanf("%d%s%d",&deg,in,&h);
		printf("Case %d: ",t);
		if(in[0]=='t'){
			int nd=(360-h%12*30)-deg;
			while(nd<=0)nd+=360;
			double kr=(double)nd/5.5*60;
			int H=(int)(kr+0.5+EPS)/3600;
			int M=(int)(kr+0.5+EPS)/60%60;
			int S=(int)(kr+EPS+0.5)%60;
			H=h-H;
			if(M||S)H--;
			M=60-M;
			if(S)M--;
			if(M==60)M=0;
			
			S=60-S;
			if(S==60)S=0;
			if(H<=0)H+=12;
			printf("%d:%02d:%02d\n",H,M,S);	
		}else{

			int nd=deg-(360-h%12*30);
			while(nd<=0)nd+=360;
			double kr=(double)nd/5.5*60;
		//	printf("%d %f\n",nd,kr);
			int H=(int)(kr+0.5+EPS)/3600;
			int M=(int)(kr+0.5+EPS)/60%60;
			int S=(int)(kr+EPS+0.5)%60;
			H+=h;
			if(H>12)H-=12;
			printf("%d:%02d:%02d\n",H,M,S);	
		}
	}
}

C: Domiyahtzee!
ただひたすらシミュレーションするだけ。やみくもに面倒なだけ。

int p[5][5]; // id
int used[7][7];
int L[13];
int R[13];
int table[5][5];
int cl[5][5];
int Y=0;
int dice(vector<int>v){
	int ko[7];
	for(int i=0;i<7;i++)ko[i]=0;
	for(int i=0;i<v.size();i++)ko[v[i]]++;
	for(int i=1;i<=6;i++){
		if(ko[i]==5){
			Y++;
			if(Y>1)return 100;
			return 50;
		}
		if(ko[i]==4){
			return i*4;
		}
	}
	for(int i=1;i<=6;i++)for(int j=i+1;j<=6;j++){
		if((ko[i]==3&&ko[j]==2)||(ko[i]==2&&ko[j]==3)){
			return 25;
		}
	}
	for(int i=1;i<=6;i++){
		if(ko[i]==3)return 3*i;
	}
	for(int i=1;i<=2;i++){
		bool ok=true;
		for(int j=0;j<5;j++){
			if(!ko[i+j])ok=false;
		}
		if(ok)return 40;
	}
	for(int i=1;i<=3;i++){
		bool ok=true;
		for(int j=0;j<4;j++){
			if(!ko[i+j])ok=false;
		}
		if(ok)return 30;
	}
	return 0;
}
int calc(){
	for(int i=0;i<5;i++){
	//	for(int j=0;j<5;j++)printf("%d",table[i][j]);
	//	printf("\n");
	}int ret=0;
	Y=0;
	for(int i=0;i<5;i++){
		vector<int>tmp;
		for(int j=0;j<5;j++)tmp.push_back(table[i][j]);
		ret+=dice(tmp);
	}
	for(int i=0;i<5;i++){
		vector<int>tmp;
		for(int j=0;j<5;j++)tmp.push_back(table[j][i]);
		ret+=dice(tmp);
	}
	vector<int>tmp;
	for(int i=0;i<5;i++)tmp.push_back(table[i][i]);
	ret+=dice(tmp);
	for(int i=0;i<5;i++)tmp[i]=table[i][4-i];
	ret+=dice(tmp);
//	printf("%d\n",ret);
	return ret;
}
char in[2];
int main(){
	int T;scanf("%d",&T);
	for(int t=1;t<=T;t++){
		int pos=0;
		for(int i=0;i<5;i++)for(int j=0;j<5;j++)p[i][j]=-1;
		for(int i=0;i<7;i++)for(int j=0;j<7;j++)used[i][j]=0;
		for(int i=0;i<13;i++){
			while(p[pos/5][pos%5]!=-1){
				pos++;
			}
			scanf("%s",in);
			if(in[0]=='V'){
				int x,y;scanf("%d%d",&x,&y);
				p[pos/5][pos%5]=p[pos/5+1][pos%5]=i;
				table[pos/5][pos%5]=x;
				table[pos/5+1][pos%5]=y;
				
				L[i]=x;
				R[i]=y;
				used[min(x,y)][max(x,y)]=1;
			}else if(in[0]=='H'){
				int x,y;scanf("%d%d",&x,&y);
				p[pos/5][pos%5]=p[pos/5][pos%5+1]=i;
				table[pos/5][pos%5]=x;
				table[pos/5][pos%5+1]=y;
				
				L[i]=x;
				R[i]=y;
				used[min(x,y)][max(x,y)]=1;
			}else{
				int x;scanf("%d",&x);
				p[pos/5][pos%5]=i;
				table[pos/5][pos%5]=x;
				
				L[i]=x;
				R[i]=0;
			}
		}
		for(int i=0;i<5;i++)for(int j=0;j<5;j++)cl[i][j]=table[i][j];
		int ret=calc();
		for(int i=0;i<13;i++){
			if(R[i]==0)continue;
			for(int j=1;j<7;j++)for(int k=1;k<7;k++){
				if(used[j][k]||used[k][j])continue;
				bool fi=true;
				for(int m=0;m<5;m++)for(int l=0;l<5;l++){
					if(p[m][l]==i){
						if(fi)table[m][l]=j;
						else table[m][l]=k;
						fi=false;
					}
				}
				ret=max(ret,calc());
				for(int m=0;m<5;m++)for(int l=0;l<5;l++)table[m][l]=cl[m][l];
			}
		}
		printf("Case %d: %d\n",t,ret);
	}
}

E: Inspectors
あの最小費用流でハミルトン路の嘘解法が作れるやつそのまま。一番楽。

int d[110][110];
int main(){
	int T;scanf("%d",&T);
	for(int t=1;t<=T;t++){
		int a;scanf("%d",&a);

		MCF::init(a*2+2);
		for(int i=0;i<a;i++){
			for(int j=i+1;j<a;j++){
				int x;scanf("%d",&x);
				d[i][j]=d[j][i]=x;
			}
		}

		for(int i=0;i<a;i++){
			for(int j=0;j<a;j++){
				if(i==j)continue;
				MCF::ae(i,j+a,1,d[i][j]);
			}
		}
		int S=a*2;
		int T=a*2+1;
		for(int i=0;i<a;i++){
			MCF::ae(S,i,1,0);
			MCF::ae(a+i,T,1,0);
		}
		MCF::solve(S,T,a);
		printf("Case %d: %d\n",t,MCF::toc);
	}
}

F: Path of Least Persistence
グラフだと思えばまあ普通の簡単な問題。実装量は多いけど

int dx[]={0,-1,1,0};
int dy[]={1,0,0,-1};
char ds[7]="ENSW";
int DX[110][110];
int DY[110][110];
char in[110];
int v[110][110];
int used[110][110];
int H,W;
void dfs(int a,int b){
	if(DX[a][b]==0&&DY[a][b]==0){
		v[a][b]=0;return;
	}
	if(v[a][b]==-3){
		v[a][b]=-1;return;
	}
	v[a][b]=-3;
	int ta=a+DX[a][b];
	int tb=b+DY[a][b];
	if(ta<0||ta>=H||tb<0||tb>=W){
		v[a][b]=-1;return;
	}
	dfs(ta,tb);
	if(v[ta][tb]>=0)v[a][b]=v[ta][tb]+1;
	else{
		v[a][b]=-1;
	}
}
int main(){
	//int T;scanf("%d",&T);
	for(int t=1;;t++){
		int a,b;scanf("%d%d",&a,&b);
		H=a;W=b;
		if(a==0)break;
		for(int i=0;i<a;i++)for(int j=0;j<b;j++){
			if(i==a-1&&j==b-1){
				DX[i][j]=DY[i][j]=0;
				continue;
			}
			scanf("%s",in);
			int len=strlen(in);
		//	printf("%s\n",in);
			int r;
			if(len==2){
				r=in[0]-'0';
				for(int k=0;k<4;k++)if(in[1]==ds[k]){
					DX[i][j]=dx[k]*r;
					DY[i][j]=dy[k]*r;
				}
			}else{
				r=(in[0]-'0')*10+in[1]-'0';
				for(int k=0;k<4;k++)if(in[2]==ds[k]){
					DX[i][j]=dx[k]*r;
					DY[i][j]=dy[k]*r;
				}
			}
		}

		for(int i=0;i<a;i++)for(int j=0;j<b;j++)used[i][j]=0;
		for(int i=0;i<a;i++){
			for(int j=0;j<b;j++){
				v[i][j]=-2;
			}
		}
		for(int i=0;i<a;i++)for(int j=0;j<b;j++){
			if(v[i][j]==-2){
				dfs(i,j);
			}
		}
		int res=v[0][0];
		if(res==-1)res=mod;
		int ans=-1;
		int R=0;
		int C=0;
		int r=0;
		int dir=0;

		int nowr=0;
		int nowc=0;
		int cnt=0;

		while(1){
			if(nowr<0||nowr>=H||nowc<0||nowc>=W)break;
			if(used[nowr][nowc])break;
			used[nowr][nowc]=1;
			if(nowr==a-1&&nowc==b-1)break;
			for(int k=1;k<100;k++)for(int l=0;l<4;l++){
				int tdx=dx[l]*k;
				int tdy=dy[l]*k;
				if(tdx==DX[nowr][nowc]&&tdy==DY[nowr][nowc])continue;
				if(nowr+tdx<0||nowr+tdx>=a)continue;
				if(nowc+tdy<0||nowc+tdy>=b)continue;
				if(v[nowr+tdx][nowc+tdy]==-1)continue;
				int cost=cnt+1+v[nowr+tdx][nowc+tdy];
				if(make_pair(make_pair(res,make_pair(R,C)),make_pair(r,dir))>make_pair(make_pair(cost,make_pair(nowr,nowc)),make_pair(k,l))){
					res=cost;ans=1;R=nowr;C=nowc;r=k;dir=l;
				}
			}
			cnt++;
			int tor=nowr+DX[nowr][nowc];
			int toc=nowc+DY[nowr][nowc];
			nowr=tor;nowc=toc;
		}
		printf("Case %d: ",t);
		if(ans==-1){
			if(res<mod)printf("none %d\n",res);
			else printf("impossible\n");
		}else{
			printf("%d %d %d%c %d\n",R,C,r,ds[dir],res);
		}

	}
}

I: Watch, Man!
実 家 の よ う な 安 心 感
サ ハ 共 和 国 の 伝 統 芸 能
狼  の  習  性

共和国向け。壁がどうくっついていようがどうでもいい。壁を全列挙して交差判定してグラフ作って流すだけ。入力の仕方も心折ってくる。EPSが大きくても小さくても落ちる。

int can[110][110];
Pt gp[110];
int gl[110];
Pt ap[110];
int al[110];
Pt tmp[200];
int type[200];
Pt tang[200];
char in[2];
int main(){
	//int T;scanf("%d",&T);
	for(int t=1;;t++){
		int a,b,c;
		scanf("%d%d%d",&a,&b,&c);
		if(a+b+c==0)break;
		for(int i=0;i<110;i++)for(int j=0;j<110;j++)can[i][j]=0;
		vector<pair<Pt,Pt> > lseg;
		vector<pair<pair<Pt, double>,pair<double,double> > > cseg;
		for(int i=0;i<a;i++){
			int n;scanf("%d",&n);
			for(int j=0;j<n;j++){
				double X,Y;
				scanf("%lf%lf%s",&X,&Y,in);
				tmp[j]=Pt(X,Y);
				if(in[0]=='s')type[j]=1;
				else type[j]=2;
				if(type[j]==2){
					scanf("%lf%lf",&X,&Y);
					tang[j]=Pt(X,Y);
				}
			}
			tmp[n]=tmp[0];
			for(int j=0;j<n;j++){
				if(type[j]==1){
					lseg.push_back(make_pair(tmp[j],tmp[j+1]));
				}else{
					Pt M1=(tmp[j]+tmp[j+1])/2;
					Pt M2=M1+(tmp[j+1]-tmp[j])*Pt(0,1);
					Pt C1=tmp[j];
					Pt C2=tmp[j]+tang[j]*Pt(0,1);
					Pt cen=pLL(M1,M2,C1,C2);
					double r=(tmp[j]-cen).ABS();
					double th1=(tmp[j]-cen).arg();
					double th2=(tmp[j+1]-cen).arg();
					if(sig((tang[j]).det(tmp[j+1]-tmp[j]))<0)swap(th1,th2);
					if(th1>th2){
						cseg.push_back(make_pair(make_pair(cen,r),make_pair(th1,PI)));
						cseg.push_back(make_pair(make_pair(cen,r),make_pair(-PI,th2)));
					}else{
						cseg.push_back(make_pair(make_pair(cen,r),make_pair(th1,th2)));
					}
				}
			}
		}

		//for(int i=0;i<cseg.size();i++)printf("Pt = (%f, %f), r = %f, th = [%f, %f]\n",cseg[i].first.first.x,cseg[i].first.first.y,cseg[i].first.second,cseg[i].second.first,cseg[i].second.second);
		for(int i=0;i<b;i++){
			double X,Y;
			scanf("%lf%lf%d",&X,&Y,al+i);
			ap[i]=Pt(X,Y);
		}
		for(int i=0;i<c;i++){
			double X,Y;
			scanf("%lf%lf%d",&X,&Y,gl+i);
			gp[i]=Pt(X,Y);
		}
		for(int i=0;i<b;i++)for(int j=0;j<c;j++){
			Pt A=ap[i];
			Pt B=gp[j];
			bool ok=true;
			for(int k=0;k<lseg.size();k++){
				if(iSS(A,B,lseg[k].first,lseg[k].second)){ok=false;break;}
			}
			if(!ok)continue;
			for(int k=0;k<cseg.size();k++){
				double dist=dLP(A,B,cseg[k].first.first);
				if(dist-EPS>cseg[k].first.second)continue;
				pair<Pt,Pt> cro=pCL(cseg[k].first.first,cseg[k].first.second,A,B);
				double th1=(cro.first-cseg[k].first.first).arg();
				double th2=(cro.second-cseg[k].first.first).arg();
				if(iSP(A,cro.first,B)==2&&cseg[k].second.first<EPS+th1&&th1<EPS+cseg[k].second.second)ok=false;
				if(iSP(A,cro.second,B)==2&&cseg[k].second.first<EPS+th2&&th2<EPS+cseg[k].second.second)ok=false;
				
			}
		//	if(ok)printf("%d %d\n",i,j);
			if(ok)can[i][j]=1;
		}
		for(int i=0;i<D_MAX_V;i++){
			D_level[i]=D_iter[i]=0;
			D_G[i].clear();
		}
		int S=b+c;
		int T=b+c+1;
		int sum=0;
		for(int i=0;i<b;i++){
			add_edge(S,i,al[i]);
			sum+=al[i];
		}
		for(int i=0;i<b;i++)for(int j=0;j<c;j++){
			if(can[i][j]){
				add_edge(i,b+j,1);
			}
		}
		for(int i=0;i<c;i++){
			add_edge(b+i,T,gl[i]);
		}
		printf("Case %d: ",t);
		if(max_flow(S,T)==sum)printf("Yes\n");
		else printf("No\n");
	}
}

G: 意味不明

vepifanov異常すぎるだろ

トロントに行きたいけどGCJは無理そうだからDCJの対策をする狼。四日目。

lispp3 Small

Largeはあまりにも虚無なので無視。
Smallの重要な点は、stackの分散のうまい方法としては、余った部分と不足部分の両方をあつめてくることで、masterで過不足がうまくあっているかを判定できる。
ただしこの問題では問題依存なテクニックが多い(+が少ないときはmasterに送る長さが短くていいとか)ので、応用性に乏しい。
気をつけるべきこととしては、masterを用意する場合は全部で99スレッドになるので、配列長が10100000では足りない。10110000にすると足りる。
smallだからというのもあるが、そこまで罠が多い問題ではない。おすすめもしないけど。

int L_ind[10110000];
char L_ch[10110000];
char R_ch[10110000];
int R_ind[10110000];
int rsz[110];
int lsz[110];
int rind[110][310];
int lind[110][310];
char lst[110][310];
char rst[110][310];
int rnew[110];
int main(){
	int T=NumberOfNodes();
	int I=MyNodeId();
	int N=GetLength();
	if(I==T-1){
		int error=N;
		int perror=N;
		for(int i=0;i<T-1;i++){
			Receive(i);
			int tmp=GetInt(i);
			if(tmp!=-1)perror=min(perror,tmp);
			rnew[i]=GetInt(i);
			rsz[i]=GetInt(i);
			for(int j=0;j<rsz[i];j++){
				rind[i][rsz[i]-1-j]=GetInt(i);
				rst[i][rsz[i]-1-j]=GetCharacter(rind[i][rsz[i]-1-j]);
			}
			lsz[i]=GetInt(i);
			for(int j=0;j<lsz[i];j++){
				lind[i][j]=GetInt(i);
				lst[i][j]=GetCharacter(lind[i][j]);
			}
		}
		int R_sz=0;
		bool ed=false;
		bool R_new=true;
		int prev=-1;
		for(int i=0;i<T-1;i++){
			long long L=(long long)N*i/(T-1);
			long long R=(long long)N*(i+1)/(T-1);
			for(int j=0;j<lsz[i];j++){
				if(R_sz==0){
					error=lind[i][j];
					ed=true;break;
				}
				if(lind[i][j]>prev+1)R_new=false;
				prev=lind[i][j];
				if(lst[i][j]=='+'){
					if(!R_new&&R_ch[R_sz-1]=='('){
						R_ch[R_sz++]='+';
						R_new=true;
					}else{
						error=lind[i][j];ed=true;break;
					}
				}else{
					if((!R_new&&R_ch[R_sz-1]=='+')||(R_new&&R_ch[R_sz-1]=='(')){
						if(!R_new)R_sz-=2;
						else R_sz--;
						R_new=false;
					}else{
						error=lind[i][j];ed=true;break;
					}
				}

			}
			if(ed)break;
			for(int j=0;j<rsz[i];j++){
				if(rind[i][j]>prev+1)R_new=false;
				prev=rind[i][j];
				if(rst[i][j]=='('){
					R_ind[R_sz]=i;
					R_ch[R_sz++]=rst[i][j];
					R_new=true;
				}else if(rst[i][j]=='+'){
					if(!R_new&&R_ch[R_sz-1]=='('){
						R_ch[R_sz++]=rst[i][j];
						R_new=true;
					}
				}
			}
			if(ed)break;
		//	R_ch[R_sz]=0;printf("%d: %s\n",R_new,R_ch);
		}
		error=min(error,perror);
		if(error==N&&R_sz==0)error=-1;
		printf("%d\n",error);
	}else{
		long long L=(long long)N*I/(T-1);
		long long R=(long long)N*(I+1)/(T-1);
		int L_sz=0;
		int R_sz=0;
		bool R_new=false;
		int error=-1;
		for(int i=L;i<R;i++){
			char ch=GetCharacter(i);
			if(ch=='('){
				R_ind[R_sz]=i;
				R_ch[R_sz++]=ch;
				R_new=true;
			}else if(ch=='+'){
				if(R_sz==0){
					L_ind[L_sz]=i;
					L_ch[L_sz++]=ch;
				}else{
					if(!R_new&&R_ch[R_sz-1]=='('){
						R_ind[R_sz]=i;
						R_ch[R_sz++]=ch;
						R_new=true;
					}else{
						error=i;break;
					}
				}
			}else{
				if(R_sz==0){
					L_ind[L_sz]=i;
					L_ch[L_sz++]=ch;
				}else{
					if((!R_new&&R_ch[R_sz-1]=='+')||(R_new&&R_ch[R_sz-1]=='(')){
						if(R_ch[R_sz-1]=='+')R_sz-=2;
						else R_sz--;
						R_new=false;
					}else{
						error=i;break;
					}
				}
			}
		}
		PutInt(T-1,error);
		int se_t=0;
		if(R_new)se_t=1;
		PutInt(T-1,se_t);
		PutInt(T-1,min(210,R_sz));
		for(int i=0;i<min(210,R_sz);i++){
			PutInt(T-1,R_ind[R_sz-1-i]);
		}
		PutInt(T-1,min(210,L_sz));
		for(int i=0;i<min(210,L_sz);i++){
			PutInt(T-1,L_ind[i]);
		}
		R_ch[R_sz]=0;
		L_ch[L_sz]=0;
	//	printf("%s\n",R_ch);
	//	printf("%s\n",L_ch);
		
		Send(T-1);
	}

}

トロントに行きたいけどGCJは無理そうだからDCJの対策をする狼。三日目。

median

これも相当厄介(めんどくささが)。配列がランダムなことからハッシュが有効だというのがわかる。さらに、この問題ではかつてのプラクティスにあったshhhで使ったテクがかなり有効利用できる。
しかしいかんせん実装量が多くて複雑でテストが微妙なので、例によって通るかどうかヒヤヒヤな問題...。なんか一箇所変えたらACになったが。変えた場所がどういう意味を持ってるのかはわからん。
変なマジックナンバーを持ち出したいときはちゃんと素数をもってきましょう。

long long D=1000000000000000LL;
pair<wolf,long long> ev[1100];
int ps[1100];
wolf pk[1100];
int rn[1100000];
int vsz[1100];
int F=33000;
int cnt[40000];
int main(){
	int T=NumberOfNodes();
	int I=MyNodeId();
	if(I==T-1){
		for(int i=0;i<1000000;i++){
			rn[i]=GetData((long long)(xrand()%1000000000000000LL));
		}
		std::sort(rn,rn+1000000);
		int Cnt=0;
		for(int i=0;i<1000000;i++){
			if(i&&rn[i]==rn[i-1])Cnt++;
			else Cnt=1;
			if(Cnt>600000){
				printf("%d\n",rn[i]);
				for(int i=0;i<T-1;i++){
					PutInt(i,0);
					Send(i);
				}
				return 0;
			}
		}
		for(int i=0;i<T-1;i++){
			PutInt(i,1);
			Send(i);
		}
		int NK=1000;
		for(int i=0;i<NK;i++){
			long long st=i*1000037;
			wolf key=0;
			wolf ks=1;
			wolf mul=1145141919;
			for(int j=0;j<100;j++){
				key*=mul;
				ks*=mul;
				key+=GetData(D+st+j);
			}
			ev[i]=make_pair(key,st);
		}
		std::sort(ev,ev+NK);
		int sz=0;
		for(int i=0;i<NK;i++){
			if(i==0||ev[i].first!=ev[i-1].first){
				pk[sz]=ev[i].first;
				ps[sz]=ev[i].second;
				sz++;
			}
		}
		for(int i=0;i<T-1;i++){
			PutInt(i,sz);
			for(int j=0;j<sz;j++){
				PutLL(i,pk[j]);
				PutLL(i,ps[j]);
			}
			Send(i);
		}
		long long tot=0;
		for(int i=0;i<T-1;i++){
			Receive(i);
			for(int j=0;j<33000;j++){
				int tmp=GetInt(i);
				cnt[j]+=tmp;
				tot+=tmp;
			}
		}
		long long now=0;
		int pind=0;
		int qind=0;
		for(int i=0;i<33000;i++){
			now+=cnt[i];
			if(now*2>tot){
				pind=i;
				now-=cnt[i];
				break;
			}
		}
		for(int i=0;i<T-1;i++){
			PutInt(i,pind);
			Send(i);
		}
		//tot=0;
		for(int i=0;i<33000;i++)cnt[i]=0;
		for(int i=0;i<T-1;i++){
			Receive(i);
			for(int j=0;j<33000;j++){
				int tmp=GetInt(i);
				cnt[j]+=tmp;
				//tot+=tmp;
			}
		}
		//now=0;
		for(int i=0;i<33000;i++){
			now+=cnt[i];
			if(now*2>tot){
				qind=i;break;
			}
		}
		printf("%d\n",pind*33000+qind);
	}else{
		Receive(T-1);
		int ch=GetInt(T-1);
		if(ch==0)return 0;
		Receive(T-1);
		int sz=GetInt(T-1);
		for(int i=0;i<sz;i++){
			pk[i]=GetLL(T-1);
			ps[i]=GetLL(T-1);
		}
		wolf key=0;
		wolf ks=1;
		wolf mul=1145141919;
		for(int i=0;i<100;i++){
			key*=mul;
			ks*=mul;
			key+=GetData(D+i);
		}
		long long ind=0;
		long long os=0;
		while(1){
			int at=lower_bound(pk,pk+sz,key)-pk;
			if(pk[at]==key){
	//			printf("%d %lld\n",ps[at],ind);
				os=ps[at]-ind;
				break;
			}
			key*=mul;
			key+=GetData(D+ind+100);
			key-=ks*GetData(D+ind);
			ind++;
		}
	//	printf("%lld\n",(os+11)%11);
		int L=sz*I/(T-1);
		int R=sz*(I+1)/(T-1);
		for(int i=L;i<R;i++){
			key=0;
			ks=1;
			mul=1145141919;

			for(int j=0;j<100;j++){
				key*=mul;
				ks*=mul;
				key+=GetData(D+ps[i]-os+j);
			}
			while(1){
				key*=mul;
				key+=GetData(D+ps[i]-os+vsz[i]+100);
				int tmp=GetData(D+ps[i]-os+vsz[i]);
				cnt[tmp/F]++;
				key-=ks*tmp;
				vsz[i]++;
				if(binary_search(pk,pk+sz,key)){
					break;
				}
			}
		}
		for(int i=0;i<33000;i++){
			PutInt(T-1,cnt[i]);
		}
		Send(T-1);
		for(int i=0;i<33000;i++)cnt[i]=0;
		Receive(T-1);
		int tar=GetInt(T-1);
		for(int i=L;i<R;i++){
			for(int j=0;j<vsz[i];j++){
				int tmp=GetData(D+ps[i]-os+j);
		//		printf("%d %lld\n",i,((ps[i]+j)%17+17)%17);
				if(tmp/F==tar)cnt[tmp%F]++;
			}
		}
		for(int i=0;i<33000;i++){
			PutInt(T-1,cnt[i]);
		}
		Send(T-1);
	}
}

トロントに行きたいけどGCJは無理そうだからDCJの対策をする狼。二日目。

baby_blocks

ヤバすぎるTime Limit設定に全アフリカが泣いた。(実は3000万回クエリ読んでも1.8秒しかかからないという罠)
偏りすぎるのがやばいけどどうすんの、ってT個のブロックに等分した後左右から別のブロックに移動するタイミング約2N個をイベントソートして先頭N個だけ使えばいいんですね。
全く難しいアイデアではないし、異様にきつい制限時間だけが厄介。本番でこれ落とした人可哀想www何この11位の人画面の隅に変なキャラクター出しながらコーディングしてるんだけどうけるwwwww

メモ: 司令塔作るときは0番ノードよりT-1番ノードにした方がやりやすい。

#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<deque>
#include<stack>
#include<string>
#include<string.h>
#include<vector>
#include<set>
#include<map>
#include<bitset>
#include<stdlib.h>
#include<cassert>
#include<time.h>
#include<bitset>
#include<message.h>
#include"baby_blocks.h"
using namespace std;
const long long mod=998244353;
const long long inf=mod*mod;
const long long d2=(mod+1)/2;
const long double EPS=1e-10;
const long double PI=acos(-1.0);
int ABS(int a){return max(a,-a);}
long long ABS(long long a){return max(a,-a);}
long double ABS(long double a){return max(a,-a);}

/*
USER'S GUIDE

Num of data / node: 1000
Amount of data / node: 8MB
Send, Receive / 5 ~ 10ms?
Linear Message passing: slow (500ms through every nodes)

HOW TO USE TOO COMPLICATED AND TOO DIFFICULT LIBRARIES
python dcj/dcj.py test --source QUESTIONNAME.cpp --nodes NUMBER_OF_NODES

FUNCTION LIBRARIES :
int NumberOfNodes();
int MyNodeId();
void PutChar(int target, char value);
void PutInt(int target, int value);
void PutLL(int target, long long value);
void Send(int target); : call this after using Put***
int Receive(int source); call this before using Get*** (return value: number of sended values)
char GetChar(int source);
int GetInt(int source);
long long GetLL(int source);
*/
long long b_sum[110];
long long a_sum[110];
long long l_sum[110];
long long r_sum[110];
int val[10100000];
pair<long long,int> ev[210];
int main(){
	int T=NumberOfNodes();
	int I=MyNodeId();
	int N=GetNumberOfBlocks();
	int bk=T;
	if(N<T){
		T=N+1;
		if(I>=T)return 0;
	}
	
	if(I==T-1){
		for(int i=0;i<T-1;i++){
			Receive(i);
			b_sum[i]=GetLL(i);
		}
		for(int i=0;i<T-1;i++){
			l_sum[i]=r_sum[i]=b_sum[i];
		}
		for(int i=0;i<T-1;i++){
			l_sum[i+1]+=l_sum[i];
		}
		for(int i=T-2;i>=0;i--){
			r_sum[i]+=r_sum[i+1];
		}
		for(int i=0;i<T-1;i++){
			ev[i*2]=(make_pair(l_sum[i],0));
			ev[i*2+1]=(make_pair(r_sum[i],1));
		}
		std::sort(ev,ev+T*2-2);
		long long Loff=0;
		long long Roff=0;
		int l_bl=0;
		int r_bl=T-2;
	//	for(int i=0;i<T;i++){
	//		printf("%lld %d\n",ev[i].first,ev[i].second);fflush(stdout);
	//	}
		for(int i=0;i<T-1;i++){

			PutLL(i,Loff);
			PutLL(i,Roff);
			PutInt(i,l_bl);
			PutInt(i,r_bl);
			Send(i);

			if(ev[i].second==0){
				Loff=ev[i].first;
				l_bl++;
			}else{
				Roff=ev[i].first;
				r_bl--;
			}
		}
		int ret=0;
		for(int i=0;i<T-1;i++){
			Receive(i);
			ret+=GetInt(i);
		}
		printf("%d\n",ret-1);
	}else{
		long long L=(long long)N*I/(T-1);
		long long R=(long long)N*(I+1)/(T-1);
		for(int i=L;i<R;i++){
			int q=GetBlockWeight(i);
			b_sum[I]+=q;
		}
		PutLL(T-1,b_sum[I]);
		Send(T-1);
		Receive(T-1);
		long long Loff=GetLL(T-1);
		long long Roff=GetLL(T-1);
		int l_bl=GetInt(T-1);
		int r_bl=GetInt(T-1);
		long long at_L=(long long)N*l_bl/(T-1);
		long long at_R=(long long)N*(r_bl+1)/(T-1)-1;
		long long n_L=(long long)N*(l_bl+1)/(T-1);
		long long n_R=(long long)N*(r_bl)/(T-1)-1;
		int ret=0;
		while(1){
			if(at_L==n_L||at_R==n_R||at_L>at_R+1)break;
		//	printf("%lld %lld %lld %lld\n",at_L,at_R,n_L,n_R);
			if(Loff==Roff){
				ret++;
				Loff+=GetBlockWeight(at_L);
				at_L++;
				Roff+=GetBlockWeight(at_R);
				at_R--;
			}else if(Loff<Roff){
				Loff+=GetBlockWeight(at_L);
				at_L++;
			}else{
				Roff+=GetBlockWeight(at_R);
				at_R--;
			}
		}
		PutInt(T-1,ret);
		Send(T-1);
	}

}

トロントに行きたいけどGCJは無理そうだからDCJの対策をする狼。一日目。

broken_memory

二分探索で変なところは探せる。3個以上のノードのデータをまとめれば、全ての答えがわかる。
hashingが難しい。2個の間違ったデータを含むときと1個も含まないときでハッシュ値がちゃんと異なるように設定しよう。

#include<stdio.h>
#include<algorithm>
#include<message.h>
#include<set>
#include"broken_memory.h"
using namespace std;

/*
USER'S GUIDE

Num of data / node: 1000
Amount of data / node: 8MB
Send, Receive / 5 ~ 10ms?
Linear Message passing: slow (500ms through every nodes)

HOW TO USE TOO COMPLICATED AND TOO DIFFICULT LIBRARIES
python dcj/dcj.py test --source QUESTIONNAME.cpp --nodes NUMBER_OF_NODES

FUNCTION LIBRARIES :
int NumberOfNodes();
int MyNodeId();
void PutChar(int target, char value);
void PutInt(int target, int value);
void PutLL(int target, long long value);
void Send(int target); : call this after using Put***
int Receive(int source); call this before using Get*** (return value: number of sended values)
char GetChar(int source);
int GetInt(int source);
long long GetLL(int source);
*/
long long in[10100000];
long long xs[10100000];
int fn[1100][2];
int pp[1100];
int ans[1100];
int main(){
	int T=NumberOfNodes();
	int I=MyNodeId();
	int N=GetLength();
	for(int i=0;i<N;i++){
		in[i]=GetValue(i);
		in[i]*=(i*i*9+i*13+14);
		in[i]+=(in[i]<<11)+(in[i]<<22)+(in[i]>>15);
		xs[i+1]=xs[i]^in[i];
	}
	if(I%5==0){
		for(int ii=1;ii<5;ii++){
			int i=I+ii;
			int left=-1;
			int right=N;
			long long tmp=0;
			while(left+1<right){
				int M=(left+right)/2;
				PutInt(i,M);
				Send(i);
				Receive(i);
				long long ff=GetLL(i);
				if(ff!=xs[M+1]){
					right=M;
					tmp=ff;
				}else{
					left=M;
				}
			}
			fn[i][0]=right;
			left=right;
			right=N;
			while(left+1<right){
				int M=(left+right)/2;
				PutInt(i,M);
				Send(i);
				Receive(i);
				long long ff=GetLL(i)^tmp;
				if(ff!=(xs[M+1]^xs[fn[i][0]+1])){
					right=M;
				}else{
					left=M;
				}
			}
			fn[i][1]=right;
			PutInt(i,1145141919);
			Send(i);
		}

		int sz=0;
		for(int ii=1;ii<5;ii++){
			int i=I+ii;
			for(int j=0;j<2;j++){
				pp[sz++]=fn[i][j];
			}
		}
		std::sort(pp,pp+sz);
		for(int i=1;i<sz;i++){
			if(pp[i]==pp[i-1]){
				ans[I]=pp[i];break;
			}
		}
		for(int ii=1;ii<5;ii++){
			int i=I+ii;
			for(int j=0;j<2;j++){
				if(fn[i][j]!=ans[I]){
					ans[i]=fn[i][j];
				}
			}
		}
		if(I==0){
			for(int i=5;i<T;i+=5){
				Receive(i);
				for(int j=0;j<5;j++){
					ans[i+j]=GetInt(i);
				}
			}
			for(int i=0;i<T;i++){
				if(i)printf(" ");
				printf("%d",ans[i]);
			}
			printf("\n");
		}else{
			for(int i=0;i<5;i++){
				PutInt(0,ans[I+i]);
			}
			Send(0);
		}

	}else{
		while(1){
			Receive(I-I%5);
			int at=GetInt(I-I%5);
			if(at==1145141919){
				break;
			}else{
				PutLL(I-I%5,xs[at+1]);
				Send(I-I%5);
			}
		}
	}
}

AGC022Cを解くのが流行っているので流行に乗った

こんなことに時間を使ってないで研究しろ

問題
C - Remainder Game

ソースコード
Submission #2409669 - AtCoder Grand Contest 022


メモ:

15:50 それでは、問題やります
15:52 問題を読んで入力しました(IMEが壊れた...)
15:53 とりあえず各操作は最大1回、greedyに最大のkを決めて好き放題判定していくだけ, nはnかn/2以下にできる
15:54 IMEが壊れてやりにくすぎる、再起動します
15:56 なんかおかしくて再起動ができない
15:58 もどってきました
16:01 最短路のor取るだけな気がしてきた

7 5
3 1

16:04 greedyの2択がめんどいんだよな
16:06 全部管理すれば良い、解けた
16:13 サンプルが通らんよ
16:15 なんでWAなんだよ 2ケースだけだから変なものあるんかな
16:18 どうせ-1のケースでしょ→やっぱりな

典型要素:

  • 2^nで1回ずつ使うやつはgreedy
  • 両側貼り合わせ
  • パソコン操作

両側貼り合わせって要は「スタートからここまで行く方法に関する情報」「ここからゴールまで行く方法に関する情報」をなんかして持っておいて途中の判定とかに使うやつなんですけども、これはAGCでばかり見ます。

圧倒的に遅いんですけども、どこが遅いのかよくわからん(最初のパソコン壊れによる消耗はかなりあるけどもそれでも遅い)。やっぱりAGCはダメですね。

2018年の目標

"一年は目標に始まり反省に終わる。"
  ーー Tozan Southerpacks

書きなぐりと言われても否定できませんが、今年の目標も書いていきましょう。全然意識してないから達成できないんだという話はしてはいけません。

競技プログラミング

枠の数が正常のオンサイトに出る

4年連続でいけたら一流の競技プログラマーでしょ。

なんか大会で優勝する

国内オンサイトかな? ひそかに狙っていきたいと思いますが、ちゃんと個数は確保されるんですかね?

天才以外お断り問題たちに光明を見つける

なんかAGCの問題への見方に変化があると嬉しいですね。

お勉強

研究

1本は雑誌に投稿したいので頑張ります。2本目が収拾つくとなお良いですね。
将来的にどの分野に進みたいかをちゃんと考えられるようにしておこう。

英語

去年はVocabularyの一年でした。当然speakingが今至急なのでspeakingを鍛える。ひとまず海外に行っても研究生活とか困らずできるレベルになるのが目標です(がこんなのどうやって評価すればいいんだ)。
あとwriting、時間との相談要素もありますが、AtCoderの問題文英訳でも関わったりとかもしたい。

他の言語

ロシア語を中級レベル目指そう。なんかあんまり国内で人気のない言語をまともなレベルまでわかるようになろう。

市町村系

また変な場所を目指して旅に出る

ここで言わなくてもやります。

🐺

🐺

いやこれ書く必要ないわ