tozangezan's diary

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

四国フォトギャラリー

2017年2月に四国に行きました。そのとき撮った写真のうち、見せたいものをただひたすら張り続けます。

f:id:tozangezan:20170220143959j:plain
番号が汚い

f:id:tozangezan:20170220151334j:plain
ラスボスがいそう

f:id:tozangezan:20170220181135j:plain
高松からは離島行きフェリーがたくさんある

f:id:tozangezan:20170220192413j:plain
セルフの醍醐味

f:id:tozangezan:20170221085950j:plain
さぬきうどん駅

f:id:tozangezan:20170221104443j:plain
徳島。駅の隣に山がある

f:id:tozangezan:20170221132720j:plain
f:id:tozangezan:20170221132810j:plain
サラダ

f:id:tozangezan:20170221133335j:plain
阿波池田。寂しすぎる

f:id:tozangezan:20170221142611j:plain
f:id:tozangezan:20170221143223j:plain
大歩危

f:id:tozangezan:20170221153217j:plain
ゆるして

f:id:tozangezan:20170221155818j:plain
日本一駅間が短い

f:id:tozangezan:20170221173917j:plain
はりまや橋

f:id:tozangezan:20170222090526j:plain
土佐湾

f:id:tozangezan:20170222092755j:plain
大都会予土線

f:id:tozangezan:20170222100512j:plain
f:id:tozangezan:20170222101938j:plain
四万十川

f:id:tozangezan:20170222102852j:plain
f:id:tozangezan:20170222102859j:plain
半家 はげ

f:id:tozangezan:20170222165503j:plain
四国一箇所巡り

f:id:tozangezan:20170222183619j:plain
願い事

ごはん
f:id:tozangezan:20170220144959j:plain
f:id:tozangezan:20170220185253j:plain
f:id:tozangezan:20170221112257j:plain
f:id:tozangezan:20170221115627j:plain
f:id:tozangezan:20170221175540j:plain
f:id:tozangezan:20170221180045j:plain
f:id:tozangezan:20170222122930j:plain
f:id:tozangezan:20170222175746j:plain

おまけ

B: flagpoles
差を取ると本当に簡単。

long long p[11000000];
long long lf[210];
long long lv[210];
long long rf[210];
long long rv[210];
long long sv[210];
int main(){
	int T=NumberOfNodes();
	int I=MyNodeId();
	int N=GetNumFlagpoles();
	if(N<=2){
		if(I==0){
			printf("%d\n",N);
		}
		return 0;
	}
	N--;
	if(N<T){
		T=N;
		if(I>=T)return 0;
	}
	int L=(long long)N*I/T;
	int R=(long long)N*(I+1)/T;
	int n=R-L;
	long long now=GetHeight(L);
	for(int i=0;i<n;i++){
		long long tmp=GetHeight(i+1+L);
		p[i]=tmp-now;
		now=tmp;
	}
	long long left=0;
	long long right=0;
	for(int i=0;i<n;i++){
		if(p[i]==p[0])left++;
		else break;
	}
	for(int i=0;i<n;i++){
		if(p[n-1-i]==p[n-1])right++;
		else break;
	}
	long long ma=0;
	long long val=0;
	for(int i=0;i<n;i++){
		if(i==0||p[i]==p[i-1]){
			val++;
		}else{
			val=1;
		}
		ma=max(ma,val);
	}
	if(I==0){
		lf[0]=p[0];
		lv[0]=left;
		rf[0]=p[n-1];
		rv[0]=right;
		sv[0]=ma;
		for(int i=1;i<T;i++){
			Receive(i);
			lv[i]=GetLL(i);
			lf[i]=GetLL(i);
			rv[i]=GetLL(i);
			rf[i]=GetLL(i);
			sv[i]=GetLL(i);
		}
		long long ret=0;
		long long nc=0;
		long long nl=0;
		for(int i=0;i<T;i++){
			ret=max(ret,sv[i]);
			if(nc==lf[i]){
				ret=max(ret,nl+lv[i]);
			}else{
				nl=0;
				nc=rf[i];
			}
			long long TL=(long long)N*i/T;
			long long TR=(long long)N*(i+1)/T;
			if(TR-TL==lv[i]){
				nl+=lv[i];
			}else{
				nl=rv[i];
				nc=rf[i];
			}
			ret=max(ret,nl);
		}
		printf("%lld\n",ret+1);
	}else{
		PutLL(0,left);
		PutLL(0,p[0]);
		PutLL(0,right);
		PutLL(0,p[n-1]);
		PutLL(0,ma);
		Send(0);
	}
}

C: number_bases
事前にくり上がりがある場合ない場合どっちも用意しておく。

int X[1100000];
int Y[1100000];
int Z[1100000];
int LL[210][2];
int RR[210][2];
int DD[210][2];
int KK[210][2];
int main(){
	int T=NumberOfNodes();
	int I=MyNodeId();
	int N=GetLength();
	if(N<T){
		T=N;
		if(I>=T)return 0;
	}
	int L=(long long)N*I/T;
	int R=(long long)N*(I+1)/T;
	int n=R-L;
	for(int i=0;i<n;i++){
		X[i]=GetDigitX(i+L);
		Y[i]=GetDigitY(i+L);
		Z[i]=GetDigitZ(i+L);
	}
	int DL=0;
	int DR=-1;
	int dame=0;
	int KR=0;
	for(int i=0;i<n;i++){
		DL=max(max(DL,Z[i]+1),max(X[i]+1,Y[i]+1));
		if(KR+X[i]+Y[i]>Z[i]){
			int nr=KR+X[i]+Y[i]-Z[i];
			if(DR==-1||DR==nr){
				DR=nr;
			}else{
				dame=1;
			}
			KR=1;
		}else if(KR+X[i]+Y[i]==Z[i]){
			KR=0;
		}else{	
			dame=1;
		}
	}
	if(DR!=-1&&DR<DL)dame=1;
	LL[I][0]=DL;
	RR[I][0]=DR;
	DD[I][0]=dame;
	KK[I][0]=KR;
	DL=0;
	DR=-1;
	dame=0;
	KR=1;
	for(int i=0;i<n;i++){
		DL=max(max(DL,Z[i]+1),max(X[i]+1,Y[i]+1));
		if(KR+X[i]+Y[i]>Z[i]){
			int nr=KR+X[i]+Y[i]-Z[i];
			if(DR==-1||DR==nr){
				DR=nr;
			}else{
				dame=1;
			}
			KR=1;
		}else if(KR+X[i]+Y[i]==Z[i]){
			KR=0;
		}else{	
			dame=1;
		}
	}
	if(DR!=-1&&DR<DL)dame=1;
	LL[I][1]=DL;
	RR[I][1]=DR;
	DD[I][1]=dame;
	KK[I][1]=KR;
	if(I==0){
	//	printf("%d: %d %d %d %d\n",0,LL[I][0],RR[I][0],DD[I][0],KK[I][0]);
		//printf("%d: %d %d %d %d\n",1,LL[I][1],RR[I][1],DD[I][1],KK[I][1]);
	//	fflush(stdout);
		for(int i=1;i<T;i++){
			Receive(i);
			for(int j=0;j<2;j++){
				LL[i][j]=GetInt(i);
				RR[i][j]=GetInt(i);
				DD[i][j]=GetInt(i);
				KK[i][j]=GetInt(i);
			}
		}
		bool ok=true;
		int dl=0;
		int dr=-1;
		int kr=0;
		for(int i=0;i<T;i++){
			if(DD[i][kr]){
				ok=false;break;
			}
			dl=max(dl,LL[i][kr]);
			if(dr!=-1&&dr!=RR[i][kr]&&RR[i][kr]!=-1){
				ok=false;
			}else if(RR[i][kr]!=-1)dr=RR[i][kr];
			kr=KK[i][kr];
		}
		if(kr)ok=false;
		if(dr!=-1&&dl>dr)ok=false;
		if(!ok){
			printf("IMPOSSIBLE\n");
		}else{
			if(dr==-1)printf("NON-UNIQUE\n");
			else printf("%d\n",dr);
		}
	}else{
		for(int i=0;i<2;i++){
		//	printf("%d: %d %d %d %d\n",i,LL[I][i],RR[I][i],DD[I][i],KK[I][i]);
			//fflush(stdout);
			PutInt(0,LL[I][i]);
			PutInt(0,RR[I][i]);
			PutInt(0,DD[I][i]);
			PutInt(0,KK[I][i]);
		}
		Send(0);
	}
}

D: broken_memory
落ちた。不必要にデータを送りすぎた。(700回ですむところを調子に乗って送りまくってしまった)

E: nanobots
smallは分割統治であることは有名。largeはたくさんスライスしてランダムに割り振ってsmallと同じことをする。

const long long mod=1000000007;
long long ret=0;
void count(long long L,long long R,long long lm,long long rm){
	if(L>=R)return;
	if(lm>rm)return;
//	printf("%lld %lld %lld %lld\n",L,R,lm,rm);
	if(Experiment(R-1,rm)=='T'){
		ret=(ret+((R-L)%mod)*((rm)%mod))%mod;
	//	printf("%lld %lld\n",R-1,rm);
		return;
	}
	if(Experiment(L,lm)=='E')return;
	long long M=(L+R)/2;
	long long left=lm-1;
	long long right=rm+1;
	while(left+1<right){
		long long mid=(left+right)/2;
		if(Experiment(M,mid)=='T'){
			left=mid;
		}else right=mid;
	}
	ret=(ret+left)%mod;
	//ret=(ret+(M-L)%mod*((left-lm+1)%mod))%mod;
	count(L,M,max(1LL,left),rm);
	count(M+1,R,lm,left);
}
int main(){
	int T=NumberOfNodes();
	int I=MyNodeId();
	int N=GetNumNanobots();
	long long R=GetRange();
	int BK=min((long long)R,2000000LL);
	
	//count(1,R+1,1,R);
	srand(1145141919);
	for(int i=0;i<BK;i++){
		int tmp=rand();
		long long left=R*i/BK+1;
		long long right=R*(i+1)/BK+1;
		if(tmp%T==I){
			count(left,right,1,R);
		}
	}
	if(I==0){
		for(int i=1;i<T;i++){
			Receive(i);
			long long tmp=GetLL(i);
			ret=(ret+tmp)%mod;
		}
		
		printf("%lld\n",ret);
	}else{
		PutLL(0,ret);
		Send(0);
	}
}

21位。なんで通ったんだろう。アイルランドでも頑張ります。