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

全探索
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

2017/06/20追記
for文の終了条件を逆にすることで1B短縮。
更にそれを利用してlの初期化を行うことで-3B+2Bの差し引き1B短縮。
コンパイラのバージョンアップにより3B短縮で計5B短縮

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=t++>>n););
	for(qsort(a,t,11,c);t;l+=!!strcmp(a[t],a[t--]));
	printf("%d",l-2);
}

197B

2017/07/25追記
strlen(gets())の代わりにreadを使うテクニックを学んだ

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

193B

メモ

yukicoderでゆるふわgolf

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