yukicoder No.3 ビットすごろく

最初の方針
「今までに到達可能な場所を元に、次に到達可能なマスを求める」という操作を、
Nマス目に到達可能になるか、「新たに到達可能になったマス」が1つもなくなるまで行う

//整数をひいてそのbitpop数を返す
int f(int x){
	int s=x%2;
	while(x/=2)s+=x%2;
	return s;
}

//今までに到達可能な場所を元に、次に到達可能なマスを求める
//「新たに到達可能になったマス」が0個なら0を、非0なら非0を返す
int g(int*a,int n){
	int b[10001],i,j,s=0;
	memcpy(b,a,n*4+4);
	for(i=1;i<=n;i++){
	//iマス目の移動先を確かめたい
		if(a[i]){
		//そもそもiマス目に来られないなら確かめる必要はない
			j=f(i);
			if(!a[i+j]){b[i+j]=1;s++;}
			if(!a[i-j]){b[i-j]=1;s++;}
		}
	}
	memcpy(a,b,n*4+4);
	return s;
}

int main(){
	int a[10001]={0,1},i,n;
	scanf("%d",&n);
	i=1;
	while(!a[n]&&g(a,n))i++;
	printf("%d",a[n]?i:-1);
	return 0;
}

長い。

ということで方針を改めた
配列に保存するものを「到達可能かどうか」ではなく「そのマスに到達するための暫定最低移動回数」とした
さらに終了条件に「到達可能なマスが増えない」を入れていたが、移動可能なマスへの移動回数がN以下であることは明らかなので
（最小回数でたどり着く際、途中同じマスを2度訪れることはないため）
情報の更新はN回行えば十分
さらにbitpopのカウントも、for文1つで書け、まとめると以下のようになる

int main(){
	int a[10030]={0,1},n,s,i,j,k;
	scanf("%d",&n);
	for(s=10000;s--;){
		for(i=0;i++<n;){
			for(j=1,k=p-a;k&=k-1;)j++;
			if(a[i]){
				if(!a[i+j]||a[i+j]>a[i])a[i+j]=a[i]+1;
				if(!a[i-j]||a[i-j]>a[i])a[i-j]=a[i]+1;
				//値を更新する条件は「まだ来たことがない」か「より小さい回数でこれた」
			}
		}
	}
	printf("%d",a[n]?a[n]:-1);
	return 0;
}

ということで、これをポインタを使ってちょっと書き換える

int main(){
	int a[10030]={0,1},n,*p,s,j,k;
	scanf("%d",&n);
	for(s=10000;s--;){
		for(p=a;++p<a+n;){
			for(j=1,k=p-a;k&=k-1;)j++;
			if(*p){
				if(!p[j]||p[j]>*p)p[j]=1+*p;
				if(!p[-j]||p[-j]>*p)p[-j]=1+*p;
			}
		}
	}
	printf("%d",a[n]?a[n]:-1);
	return 0;
}

あとは単純な圧縮……だけど、大変なので1ステップずつ
まずは自明なところ

a['~~'],*p,s=1e4,n,k;
main(j){
	for(a[1]=scanf("%d",&n);s--;){
		for(p=a;++p<a+n;){
			for(j=1,k=p-a;k&=k-1;)j++;
			*p&&(
				!p[j]|p[j]>*p?p[j]=1+*p:0,
				!p[-j]|p[-j]>*p?p[-j]=1+*p:0;
			)
		}
	}
	n=!printf("%d",*p-!*p);
	//ループ終了時p=a+nとなっているので
}

*p&&(hoge)をfor文の中にしまって

a['~~'],*p,s=1e4,n,k;
main(j){
	for(a[1]=scanf("%d",&n);s--;)
		for(p=a;++p<a+n;*p&&(!p[j]|p[j]>*p?p[j]=1+*p:0,!p[-j]|p[-j]>*p?p[-j]=1+*p:0))
			for(j=1,k=p-a;k&=k-1;)j++;
	n=!printf("%d",*p-!*p);
}

jの初期化に*p&&(hoge)を利用することにして

a['~~'],*p,s=1e4,n,k;
main(j){
	for(a[1]=scanf("%d",&n);s--;)
		for(p=a;++p<a+n;j=!*p||(!p[j]|p[j]>*p?p[j]=1+*p:0,!p[-j]|p[-j]>*p?p[-j]=1+*p:1))
			for(k=p-a;k&=k-1;)j++;
	n=!printf("%d",*p-!*p);
}

ループを圧縮

a['~~'],*p,s=1e4,n,k;
main(j){
	for(a[1]=scanf("%d",&n);s--;)
		for(p=a;!(k&=k-1)?j=!*p||(!p[j]|p[j]>*p?p[j]=1+*p:0,!p[-j]|p[-j]>*p?p[-j]=1+*p:1),k=++p-a,k*=k<n:++j;);
	n=!printf("%d",*p-!*p);
}

kの代入とループの終了条件を噛みあわせるためにk*=k<nという処理をしている
（内側のループが終わる毎に、kには0か1が代入されていて欲しい
　さもないと、a[0]!=0となった2回目以降のループにおいて、1回目の!*p||(hoge)の部分でバグる）

この圧縮によって、p=aのときも更新チェックを行うようになったので、これを利用して
main第一引数のjが1で初期化されていることを組み合わせると
配列に保存するものを「最小回数」から「最小回数+1」にするようにすれば入出力が改善され
以下の181Bになる

a['~~'],*p,s=1e4,n,k;
main(j){
	for(*a=scanf("%d",&n);s--;)
		for(p=a;!(k&=k-1)?j=!*p||(!p[j]|p[j]>*p?p[j]=1+*p:0,!p[-j]|p[-j]>*p?p[-j]=1+*p:1),k=++p-a,k*=k<n:++j;);
	n=!printf("%d",*p-1);
}

さらに外側のループを圧縮するも、pの初期化で2B、出力で2B増え、自分の腕では同じ181Bにしかならなかった

a['~~'],*p=a,s=1e4,n,k;
main(j){
	for(*a=scanf("%d",&n);!(k&=k-1)?j=!*p||(!p[j]|p[j]>*p?p[j]=1+*p:0,!p[-j]|p[-j]>*p?p[-j]=1+*p:1),++p-a>n?p=a,s--:(k=p-a):++j;);
	n=!printf("%d",a[n]-1);
}

ここでは、j=!*p||(hoge)の処理が終わった時点ではk=0であることを利用している
先程に比べ、p=a+nの場合でもループが実行されるがこれは問題ない
（a+nから配る先は、a[n]+1以上の値しか入らないので、再度a+nが更新されたとしても、（その値はa[n]以下なので）関与しない）

メモ

yukicoderでゆるふわgolf

yukicoder No.3 ビットすごろく