yukicoder No.7 プライムナンバーゲーム

「場にある数がnのとき先攻後攻どちらが勝てるか」をnが小さい方から埋めていけばよい
「∃p:素数.場にある数がn-pのとき後攻が勝てる」なら先攻が勝てる。さもなくば後攻が勝つ

int main(){
	int p[1300]={},w[10001]={},n,s,i,j;
	//wには勝敗を保存する。先攻が勝てるなら0,後攻が勝てるなら1
	//w[0]=w[1]=0（場の数が0or1でターンが回ってきたら勝ち）
	scanf("%d",&n);
	for(i=2;i<=n;i++){
		for(j=0;p[j]&&i%p[j];j++);
		if(!p[j])p[s++]=i;
		//素数で割り切れるor既知の素数が尽きるまでループ
		//既知の素数が尽きたことでループを抜けていたならiは素数
	}
	for(i=2;i<=n;i++){
		for(s=j=0;p[j]&&p[j]<=i;j++)s+=w[i-p[j]];
		w[i]=!s;
		//n-pで後攻が勝てるものが1つでもあればsは非0、さもなくば0
	}
	n=!puts(w[n]?"Lose":"Win");
}

自明なところ

p[1300],w['~~'],n,s,j;
main(i){
	for(scanf("%d",&n);j=i++<n;i==j?p[++s]=i:0)for(;i%++j;);
	//iが素数かどうかの判定に既知の素数を利用するのをやめ、普通に2からiで割る
	for(i=1;i++<n;w[i]=!s)for(s=j=0;p[++j]&&p[j]<=i;s+=w[i-p[j]]);
	n=!puts(w[n]?"Lose":"Win");
}

ポインタを使う

p[1300],w['~~'],n,s,*q=p;
main(i){
	for(scanf("%d",&n);s=i++<n;i==s?*++q=i:0)for(;i%++s;);
	for(i=1;i++<n;w[i]=!s)for(s=0,q=p;*++q&&*q<=i;s+=w[i-*q]);
	n=!puts(w[n]?"Lose":"Win");
}

ループ圧縮

p[1300],w['~~'],n,s,*q=p;
main(i){
	for(scanf("%d",&n);i%++s?:(i==s?*q++=i:0,s=i++<n););
	//iが1のときも処理されるようになったので、p[0]=1とする
	for(i=2;!*++q|*q>i?w[i]=!s,s=0,q=p,i++<n:(s+=w[i-*q],1););
	n=!puts(w[n]?"Lose":"Win");
}

s+=w[i-*q]が0のこともあるせいで冗長だなあ…　→　sの初期値を1にしよう

for(i=2;!*++q|*q>i?w[i]=!s,s=0,q=p,i++<n:(s+=w[i-*q],1););
が
for(i=1;!*++q|*q>i?w[i]=!~-s,s=1,q=p,i++<n:(s+=w[i-*q]););
//1回目はsが0なのでiの初期値をずらした

//これだけだと文字数が変わらないが、三項演算子の分岐のどちらにもsへの代入があるのでまとめられ
for(i=1;s=!*++q|*q>i?w[i]=!~-s,q=p,i++<n:s+w[i-*q];);
//とできる。さらに出力部分もまとめて
for(i=1;s=!*++q|*q>i?w[i]=!~-s,q=p,i++<n||!puts(w[n]?"Lose":"Win"):s+w[i-*q];);

ということで

p[1300],w['~~'],n,s,*q=p;
main(i){
	for(scanf("%d",&n);i%++s||(i==s?*q++=i:0,s=i++<n););
	for(i=1;s=!*++q|i<*q?w[i]=!~-s,q=p,i++<n||!puts(w[n]?"Lose":"Win"):s+w[i-*q];);
}

ここで天啓
配列を逆にしよう！
つまりiの勝敗をw[n-i]に保存することにする
こうすると、w[i-*q]の部分でi-*q<0とならないようにするための条件i<*qが不要になる
さらに出力もw[n]でなく*wで判定できる
加えて変数iが不要になる……のだが、これは短縮にならなかった

p[1300],w['~~'],n,s,*q=p;
main(i){
	for(scanf("%d",&n);i%++s||(i==s?*q++=i:0,s=i++<n););
	for(n--;s=!*++q?w[n]=!~-s,q=p,n--||!puts(*w?"Lose":"Win"):s+w[n+*q];);
	//nの元からの減分がiの代わりになっている
}

最後にループ圧縮
そのままだとsがダメになるので別変数tを用意

p[1300],w['~~'],n,s,t,*q=p;
main(i){
	for(scanf("%d",&n),n-=2;s=i%++t||(i==t?*q++=i:0,t=i++<n)?:!*++q?w[n]=!~-s,q=p,n--||!puts(*w?"Lose":"Win"):s+w[n+*q];);
}

初めて後半に入る時点でs=1になっているので、前までと同じように2から始められるよう、nを2減らしておく
前半の時点でnを減らしていても良いのは、n-1,nが素数だとしてもそれを言うことはありえない（言うと負ける）から
また、一度前半が偽になれば再び真になることはなく、後半に影響もない
なぜなら偽になった時点でiはn+1,tは0になっているので、i%++t、i==t、i++<nはいずれも常に偽となるから。
以上154B

17/01/24追記
!~-sはsが1以上であることから1/sと書けるので1B短縮

p[1300],w['~~'],n,s,t,*q=p;
main(i){
	for(scanf("%d",&n),n-=2;s=i%++t||(i==t?*q++=i:0,t=i++<n)?:!*++q?w[n]=1/s,q=p,n--||!puts(*w?"Lose":"Win"):s+w[n+*q];);
}

153B

メモ

yukicoderでゆるふわgolf

yukicoder No.7 プライムナンバーゲーム