メモ

yukicoderでゆるふわgolf

yukicoder No.524 コインゲーム

問題はこちら
No.524 コインゲーム - yukicoder

Nimなので問題は「1～Nまでxorをとったものが0か否か判定せよ」と読み替えられる。（このことの証明は以前した：yukicoder No.2 素因数ゲーム - メモ）
以下では「1～Nまでのxorをとったもの」をxor和と呼ぶことにする
・最下位bitについて
xor和の最下位bitをN=1のときから順に並べると1,1,0,0,…という長さ4の周期性を持つことがわかる
（次にxorするのが0or1、今の値が0or1、の4通りの状態しかないことから明らか）
よって　xor和の最下位bitが0⇔N≡3,0 mod 4
・それ以上の位について
xor和の最下位bitを除いたものをN=1のときから順に並べると　0、非0、0、非0…という長さ2の周期性を持つことがわかる
これは偶数kに対し、kとk+1は最下位bitを除いて等しいことと、同じ値同士のxorは0になることからわかる
よって xor和の最下位bit以外が0⇔Nが奇数

この2つをあわせて、xor和が0⇔N≡3 mod 4がわかる

n;main(){putchar(~atoi(gets(&n))%4?79:88);}

43B
nをmainの引数とするとセグフォ

2017/08/12追記
putsの方が短かった

n;main(){puts(~atoi(gets(&n))%4?"O":"X");}

42B

yukicoder No.523 LED

問題はこちら
No.523 LED - yukicoder

1～Nを2個ずつ並べる重複順列なので(2N)!/2^N
mod Pでの階乗やべき乗、逆元を計算する関数を持っているならこれをそのまま投げても良いでしょう

#define ll long long
ll pom(ll a,ll n,int m){ll x=1;for(a%=m;n;n/=2)n%2?x=x*a%m:0,a=a*a%m;return x;}
#define invp(a,p)pom(a,p-2,p)
ll factm(int n,int m){ll x=1;while(n)x=x*n--%m;return x;}

n,m=1000000007;
main(){
	scanf("%d",&n);
	printf("%d",factm(2*n,m)*invp(pom(2,n,m),m)%m);
}

少し式変形を考えるともう少し簡単になる
2N!=\prod_{k=1}^N (2k-1)2k　なので　\frac{2N!}{2^N}=\prod_{k=1}^N (2k-1)k
これを使えば単なるループで書ける

i,n,s,m=1000000007;
main(){
	scanf("%d",&n);
	s=1;
	for(i=1;i<=n;i++)s=1L*s*i%m*(2*i-1)%m;
	printf("%d",s);
}

無駄な1Lがなくなるようにぐっと睨んで

n,m=1e9+7;main(s){for(scanf("%d",&n);n;s=s*(2*n-1L)%m*n--%m);printf("%d",s);}

77B

yukicoder No.522 Make Test Cases(テストケースを作る)

問題はこちら
No.522 Make Test Cases(テストケースを作る) - yukicoder

a,b,cの三重ループでやると間に合わないという罠がある
a,bを決めればcが自動的に決まるので二重ループで書ける
似たような話は前にNo.250 atetubouのzetubou - yukicoderの問題文で見た

a,b,c,n;
main(){
	scanf("%d",&n);
	for(a=1;a<n;a++)for(b=a;b<n;b++){
		c=n-a-b;
		if(c>=b)printf("%d %d %d\n",a,b,c);
	}
}

2つ目のループの継続条件をn-a-b>=bにすると、c>=bかどうかの分岐が不要になる
ということでループ圧縮などをささっと

i,j;main(n){for(scanf("%d",&n);i<n;i++)for(j=i;n-i-j>=j;j++)printf("%d %d %d\n",i,j,n-i-j);}
i,j;main(n){for(scanf("%d",&n);j=++i%n;)for(;n-i-j>=j;)printf("%d %d %d\n",i,j++,n-i-j);}
n,j;main(i){for(j=scanf("%d",&n);n-i-j>=j?printf("%d %d %d\n",i,j++,n-i-j):(j=++i%n););}
n,j;main(i){for(j=scanf("%d",&n);n-i-j<j?j=++i%n:printf("%d %d %d\n",i,j++,n-i-j););}

85B

yukicoder No.521 Cheeses and a Mousetrap(チーズとネズミ捕り)

問題はこちら
No.521 Cheeses and a Mousetrap(チーズとネズミ捕り) - yukicoder

K=0及びK>Nのときは0。
そうでないとき、該当する箱はK番目かN+1-K番目。この2つが一致するとき危険は箱は1つで、一致しないとき2つ。

n,k;
main(){
	scanf("%d%d",&n,&k);
	if(k==0||k>n)printf("0");
	else if(k==n+1-k)printf("%d",n-1);
	else printf("%d",n-2);
}

ぎゅっとするだけ。条件分岐はどちらでも同じになった

main(n,k){scanf("%d%d",&n,&k);printf("%d",!k|k>n++?0:n-3+!(n-k-k));}
main(n,k){scanf("%d%d",&n,&k);printf("%d",k&&k<++n?n-3+!(n-k-k):0);}

68B