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

メモ

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

yukicoder No.52 よくある文字列の問題

問題はこちら
No.52 よくある文字列の問題 - yukicoder

全探索
Cだと、重複を除いた要素数を数えたり、文字列の集合を作ったり、いちいち困難

char s[11],a[1030][11];
int c(char*a,char*b){return strcmp(a,b);}
int main(){
	int t,l,r,n,i;
	n=strlen(gets(s));
	for(t=0;t<1<<n;t++){
	//先頭から取るか末尾から取るか、2^nの選択肢がある
	//(最後の1文字はどっちでも同じなので実質2^(n-1)だが)
		l=0;r=n;
		for(i=0;i<n;i++)a[t][i]=s[t&1<<i?l++:--r];
		//tを長さnのbit列と見て、bitが1なら左から、0なら右からとるとする
	}
	qsort(a,1<<n,11,c);
	t=0;
	for(i=0;i<1<<n;i++)t+=!!strcmp(a[i],a[i+1]);
	//a[1<<n]は空文字列になっている
	printf("%d",t);
	return 0;
}

ちゃちゃっと縮める

char s[11],a[1030][11];
t,l,r,n;
c(a,b){l=strcmp(a,b);}
main(i){
	for(n=strlen(gets(s));t++<1<<n;l=0)for(i=r=n;i--;a[t][i]=s[t&1<<i?l++:--r]);
	//上ではtは0~(1<<n)-1だったが1~1<<nになった。下nbitしか見てない影響はない
	//a[0]が空のままになった
	//iの初期化をサボるため、a[t]には、新しい文字列が逆順で保存される
	//(同じかどうかさえ確認できれば良いのでこれで構わない)
	for(qsort(a,t,11,c);t--;i+=!!strcmp(a[t+1],a[t]));
	//前のループが終わった時点でtは(1<<n)+1になっている
	//上ではa[0],a[1],…,a[(1<<n)-1],a[1<<n](空)を見ていたが
	//ここではa[0](空),a[1],…,a[(1<<n)-1],a[1<<n],a[(1<<n)+1](空)を見ている
	//そのため加算が1回多いのでiの初期値-1を利用している
	t=!printf("%d",i);
}

for(qsort(a,t,11,c);t--;i+=!!strcmp(a[t+1],a[t]));
の部分を処理系依存未定義動作で
for(qsort(a,t,11,c);t;i+=!!strcmp(a[t],a[t--]));
に書き換えて2B短縮

for文を圧縮したいのだが、結局-1のつじつま合わせが難しく、同じ長さにしかならなかった

char s[],a[1030][11];
r,t,i,n;
c(a,b){r=strcmp(a,b);}
main(l){
	for(n=strlen(gets(s));i--?a[t][i]=s[t&1<<i?++l:--r]:(i=r=n,l=-1,t++<1<<n););
	for(qsort(a,t,11,c);t;l+=!!strcmp(a[t],a[t--]));
	r=!printf("%d",l);
}

202B