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

メモ

yukicoderで遊んでいる競プロゆるふわ勢

yukicoder No.402 最も海から遠い場所

問題はこちら
No.402 最も海から遠い場所 - yukicoder

初見では解説の「無駄解法」と同じことしか思いつけなかったので、解説を見て回答

陸の部分からなる最大の正方形を見つける問題と同値になる

#define max(p,q)(p>q?p:q)
#define min(p,q,r)(p<q?p<r?p:r:q<r?q:r)
int a[3010][3010];
main(){
	int i=1,j,t,s;
	gets(&t);//H,Wは要らないので読み捨て
	//a[i][j]は1-basedなindexとする(i-1,j-1でout of rangeにならないようにするため)
	while(t=~getchar()){
		j++;
		if(t==~'#'){
			a[i][j]=min(a[i-1][j],a[i-1][j-1],a[i][j-1])+1;
			s=max(s,a[i][j]);
		}
		else if(t==~'\n'){i++;j=0;}
	}
	printf("%d",(s+1)/2);
	return 0;
}

取り敢えず縮める

a[3010][3010];
j,t,s;
main(i){
	for(gets(&t);t=~getchar();~t&1?s=fmax(s,a[i][j]=fmin(fmin(a[i-1][j],a[i-1][j-1]),a[i][j-1])+1):t&4?j=!++i:0)j++;
	s=!printf("%d",-~s/2);
}

~t&1としている所を素直に~t==35と書けば最初のgetsが省略できる
2次元配列は面倒だからポインタを使ったほうが良さそう
改行の際に飛ぶ先を保存するのはint*とintどっちがいいか考える必要がありそう
ポインタを使うならindexは1つずらしてa[i+1][j+1]=fmin(fmin(a[i][j],a[i+1][j]),a[i][j+1])とした方が都合が良さそう

a[1<<24];
*p=a,*q;
M=4e3,s;
main(t){
	for(;t=~getchar();q++)~t==35?s=fmax(s,q[M+1]=fmin(fmin(*q,q[1]),q[M])+1):t&4?q=p+=M:0;
	//*pの代わりにint型変数pを使って
//	for(;t=~getchar();q++)~t==35?s=fmax(s,q[M+1]=fmin(fmin(*q,q[1]),q[M])+1):t&4?q=a+(p+=M):0;
	//とすると、この部分が+4B、初期化が-3Bでトータル1B損
	s=!printf("%d",-~s/2);
}

142B